#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[500009],ans[500009],x[10],l,r,fen[500009];
pair <pair <int, int>, int> p[500009];
map <int, vector <int> > m;
int read(int q){
q=500002-q;
int jm=0;
while(q>=1){
jm+=fen[q];
q=q-(q&(-q));
}
return jm;
}
void upd(int q, int w){
q=500002-q;
while(q<=500003){
fen[q]+=w;
q=q+(q&(-q));
}
}
void updd(int q, int w, int rr){
if(q>w) return;
upd(w,rr);
upd(q-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(t=1; t<=tes; t++){
cin>>p[t].first.first>>p[t].first.second;
p[t].second=t;
}
sort(p+1,p+tes+1);
r=0;
for(t=1; t<=tes; t++){
while(r<p[t].first.second){
r++;
for(j=0; j<=4; j++) x[j]=0;
if(m[f[r]].size()>=1){
j=0;
for(i=m[f[r]].size()-1; i>=0; i--){
j++;
if(j>3) break;
x[j]=m[f[r]][i];
}
}
m[f[r]].push_back(r);
updd(x[2]+1,x[1],1);
updd(x[3]+1,x[2],-1);
}
ans[p[t].second]=read(p[t].first.first);
}
for(t=1; t<=tes; t++){
cout<<ans[t]<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 4 |
Incorrect |
14 ms |
620 KB |
Output isn't correct |
| 5 |
Incorrect |
270 ms |
5100 KB |
Output isn't correct |
| 6 |
Incorrect |
275 ms |
5120 KB |
Output isn't correct |
| 7 |
Incorrect |
587 ms |
10092 KB |
Output isn't correct |
| 8 |
Incorrect |
906 ms |
15596 KB |
Output isn't correct |
| 9 |
Incorrect |
1183 ms |
20144 KB |
Output isn't correct |
| 10 |
Incorrect |
1487 ms |
24404 KB |
Output isn't correct |
