SPOJ Problem:- D-Query Solution 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
    //NAME:- ANUHAR TRIPATHI
    //COLLEGE:- JAYPEE UNIVERSITY OF ENGINEERING & TECHNOLOGY, GUNA
    //EMAIL:- anuhartripathi15@gmail.com
    //SPOJ Problem:-  D-query
    #include<bits/stdc++.h>
    #define ll long long
    #define bb 555
    using namespace std;
    class node
    {
        public:
        ll l,r,i;
    };
    bool cmp(node x, node y)
    {
        if(x.l/bb!=y.l/bb)
        return x.l/bb<y.l/bb;
        //else if(x.l==y.l)
        return x.r<y.r;
    }
    int main()
    {
        ll n,m;
        cin>>n;
        ll a[n],i;
        for(i=0;i<n;i++)cin>>a[i];
        //memset(a,0,sizeof(a)/sizeof(a[0]));
        cin>>m;
        node q[m];
        for(i=0;i<m;i++)
        {
            cin>>q[i].l>>q[i].r;
            q[i].l--;       q[i].r--;
            q[i].i=i;
        }
        sort(q,q+m,cmp);
        ll co[1000010];
        memset(co,0,sizeof(co)/sizeof(co[0]));
        ll st,end,res[m];          st=end=0;
        //co[a[q[0].l]]++;
        ll ans=0;
        for(i=0;i<m;i++)
        {
            while(st<q[i].l)
            {
                co[a[st]]--;
                if(co[a[st]]==0)    ans--;
                st++;
            }
            while(st>q[i].l)
            {
                co[a[st-1]]++;
                if(co[a[st-1]]==1)    ans++;
                st--;
            }
            while(end<=q[i].r)
            {
                co[a[end]]++;
                if(co[a[end]]==1)    ans++;
                end++;
            }
            while(end>q[i].r+1)
            {
                co[a[end-1]]--;
                if(co[a[end-1]]==0)    ans--;
                end--;
            }
            res[q[i].i]=ans;
        }
        for(i=0;i<m;i++)cout<<res[i]<<"\n";
        return 0;
    }

Comments

Post a Comment

Popular posts from this blog

SPOJ Problem:- PARTY - Party Schedule Solution

Read the comment for explanation. You can remove the unnecessary comments. Copy the code to your IDE for better reading then read the explanations from comment lines in code. Also please send your feed-backs.  You can see youtube video of "Tushar Roy" on knapsack problem.  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 //NAME:- ANUHAR TRIPATHI //COLLEGE:- JAYPEE UNIVERSITY OF ENGINEERING & TECHNOLOGY, GUNA //EMAIL:- anuhartripathi15@gmail.com //SPOJ Problem:- PARTY - Party Schedule # include < bits / stdc ++ .h > # define ll long long using namespace std; int main () { ll b,n,i,fee,fun; cin >> b >> n; while (b != 0 || n != 0 ) { ll a[n + 2 ][b + 3 ]; for (i = 0 ;i < b + 1 ;i ++ ) {a[ 0 ][i + ...
Read more

SPOJ Problem:- AMR10G - Christmas Play Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 //NAME:- ANUHAR TRIPATHI //COLLEGE:- JAYPEE UNIVERSITY OF ENGINEERING & TECHNOLOGY, GUNA //EMAIL:- anuhartripathi15@gmail.com //SPOJ Problem:- AMR10G - Christmas Play # include < bits / stdc ++ .h > # define ll long long using namespace std; int main () { ll t; cin >> t; while (t -- ) { ll n,k; cin >> n >> k; ll h[n],i,j,mi = LONG_MAX; for (i = 0 ;i < n;i ++ ) cin >> h[i]; sort(h,h + n); j = 0 ; for (i = k - 1 ;i < n;i ++ ) { if (mi > h[i] - h[j]) mi = h[i] - h[j]; ++ j; } cout << mi << " \n " ; } return 0 ; } ...
Read more

SPOJ Problem:- HORRIBLE - Horrible Queries Solution

Copy the code to your IDE for better reading then read the explanations from comment lines in code. Also please send your feed-backs.  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 //NAME:- ANUHAR TRIPATHI //COLLEGE:- JAYPEE UNIVERSITY OF ENGINEERING & TECHNOLOGY, GUNA //EMAIL:- anuhartripathi15@gmail.com //SPOJ Problem:- HORRIBLE - Horrible Queries # include < bits / stdc ++ .h > # define ll long long using namespace std; vector < ll > tree( 800050 ); //,kk=0; vector < ll > lazy( 800050 ); /*In update function I have avoided updating whole tree, if in any case a node with all its children needs to be updated then I do not go to its children for upda...
Read more