oj.uz

Submission #85792

# Submission time Handle Problem Language Result Execution time Memory
85792 2018-11-21T14:35:56 Z Vasiljko Poklon (COCI17_poklon) C++14
140 / 140
 1075 ms 40020 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;
const int N = 5e5+5;
const int SZ = 710;

struct Query{
    int l,r,ind;
    Query(int _l=0,int _r=0,int _ind=0){
        l=_l;r=_r;ind=_ind;
    }

    bool operator < (const Query &p)const {
        if(l/SZ!=p.l/SZ)return l/SZ<p.l/SZ;
        return r<p.r;
    }
};

int n,q,a[N],cnt[N],sol,ans[N];
Query b[N];
vector<int>c;

void Add(int ind){
    if(cnt[a[ind]]==1)sol++;
    else if(cnt[a[ind]]==2)sol--;
    cnt[a[ind]]++;
}

void Del(int ind){
    if(cnt[a[ind]]==3)sol++;
    else if(cnt[a[ind]]==2)sol--;
    cnt[a[ind]]--;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        c.push_back(a[i]);
    }
    sort(c.begin(),c.end());
    c.erase(unique(c.begin(),c.end()),c.end());

    for(int i=1;i<=n;i++){
        a[i]=lower_bound(c.begin(),c.end(),a[i])-c.begin()+1;
    }

    for(int i=1;i<=q;i++){
        cin>>b[i].l>>b[i].r;
        b[i].ind=i;
    }
    sort(b+1,b+1+q);
    int l=0,r=0;
    for(int i=1;i<=q;i++){
        while(l<b[i].l)Del(l++);
        while(l>b[i].l)Add(--l);
        while(r<b[i].r)Add(++r);
        while(r>b[i].r)Del(r--);

        ans[b[i].ind]=sol;
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6264 KB Output is correct
2 Correct 8 ms 6392 KB Output is correct
3 Correct 9 ms 6392 KB Output is correct
4 Correct 13 ms 6552 KB Output is correct
5 Correct 122 ms 9428 KB Output is correct
6 Correct 119 ms 10992 KB Output is correct
7 Correct 327 ms 15764 KB Output is correct
8 Correct 559 ms 22092 KB Output is correct
9 Correct 805 ms 30244 KB Output is correct
10 Correct 1075 ms 40020 KB Output is correct