Submission #339666

# Submission time Handle Problem Language Result Execution time Memory
339666 2020-12-25T19:52:42 Z mosiashvililuka Poklon (COCI17_poklon) C++14
0 / 140
1487 ms 24404 KB
#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