제출 #577606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577606		mosiashvililuka	Poklon (COCI17_poklon)	C++14	0 / 140	382 ms	28884 KiB

poklon

#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: 0 / 140