oj.uz

Submission #339667

# Submission time Handle Problem Language Result Execution time Memory
339667 2020-12-25T19:56:01 Z mosiashvililuka Poklon (COCI17_poklon) C++14
140 / 140
 1489 ms 16108 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;
		swap(p[t].first.first,p[t].first.second);
		p[t].second=t;
	}
	sort(p+1,p+tes+1);
	for(t=1; t<=tes; t++) swap(p[t].first.first,p[t].first.second);
	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;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 14 ms 492 KB Output is correct
5 Correct 274 ms 3436 KB Output is correct
6 Correct 276 ms 3544 KB Output is correct
7 Correct 590 ms 6764 KB Output is correct
8 Correct 916 ms 10604 KB Output is correct
9 Correct 1197 ms 13692 KB Output is correct
10 Correct 1489 ms 16108 KB Output is correct