제출 #339667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339667		mosiashvililuka	Poklon (COCI17_poklon)	C++14	140 / 140	1489 ms	16108 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],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 / 140