oj.uz

Submission #577612

# Submission time Handle Problem Language Result Execution time Memory
577612 2022-06-15T06:34:58 Z mosiashvililuka Poklon (COCI17_poklon) C++14
140 / 140
 391 ms 28896 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[500009],v[500009][4],fen[500009],ans[500009];
map <int, int> mp;
map <int, int>::iterator TA;
vector <pair <int, int> > V[500009];
void upd(int q, int w){
    while(q<=500004){
        fen[q]+=w;
        q=q+(q&(-q));
    }
}
int read(int q){
    int sm=0;
    while(q>0){
        sm+=fen[q];
        q=q-(q&(-q));
    }
    return sm;
}
void UPD(int q, int w, int rr){
    upd(q,rr);upd(w+1,-rr);
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>tes;
    for(i=1; i<=a; i++) cin>>f[i];
    for(i=1; i<=a; i++){
        mp[f[i]]=1;
    }
    zx=0;
    for(TA=mp.begin(); TA!=mp.end(); TA++){
        zx++;(*TA).second=zx;
    }
    for(i=1; i<=a; i++){
        f[i]=mp[f[i]];
    }
    for(t=1; t<=tes; t++){
        cin>>c>>d;
        V[d].push_back({c,t});
    }
    for(i=1; i<=a; i++){
        if(v[f[i]][0]!=0){
            UPD(v[f[i]][1]+1,v[f[i]][0],1);
        }
        if(v[f[i]][1]!=0){
            UPD(v[f[i]][2]+1,v[f[i]][1],-1);
        }
        for(vector <pair <int, int> >::iterator it=V[i].begin(); it!=V[i].end(); it++){
            ans[(*it).second]=read((*it).first);
        }
        for(j=2; j>=1; j--){
            v[f[i]][j]=v[f[i]][j-1];
        }
        v[f[i]][0]=i;
    }
    for(t=1; t<=tes; t++){
        cout<<ans[t]<<"\n";
    }
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 66 ms 15444 KB Output is correct
6 Correct 77 ms 15424 KB Output is correct
7 Correct 150 ms 18736 KB Output is correct
8 Correct 224 ms 22240 KB Output is correct
9 Correct 368 ms 25572 KB Output is correct
10 Correct 391 ms 28896 KB Output is correct