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:- GSS3 - Can you answer these queries III 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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 //NAME:- ANUHAR TRIPATHI //COLLEGE:- JAYPEE UNIVERSITY OF ENGINEERING & TECHNOLOGY, GUNA //EMAIL:- anuhartripathi15@gmail.com //SPOJ Problem:- GSS3 - Can you answer these queries III # include < bits / stdc ++ .h > # define ll long long using namespace std; class node { public: ll suf,pre,result,sum; }tree[ 131080 ]; ll a[ 131080 ]; void build (ll l, ll r, ll pos) { if (l == r) { tree[pos].sum = tree[pos].pre = tree[pos].suf = tree[pos].result = a[l]; return ; } ll mid = (l + r) / 2 ; build(l,mid,pos * 2 ); build(mid + 1 ,r,po
Read more