Submission #1273449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273449		i271828	Poklon (COCI17_poklon)	C++20	140 / 140	4275 ms	385252 KiB

poklon

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int MAX=500005;

struct ST{
	int s,e,m;
	vector<int> A;
	ST *l,*r;
	ST(int s,int e,int* B){
		this->s=s;
		this->e=e;
		m=(s+e)>>1;
		if (s==e){
			A.push_back(B[s]);
			return;
		}
		l=new ST(s,m,B);
		r=new ST(m+1,e,B);
		A.resize(l->A.size()+r->A.size());
		merge(l->A.begin(),l->A.end(),r->A.begin(),r->A.end(),A.begin());
	}
	int qry(int x,int y,int a){
		if (x<=s&&y>=e){
			//cout<<A.end()-upper_bound(A.begin(),A.end(),a)<<'\n';
			return A.end()-upper_bound(A.begin(),A.end(),a);
		}
		if (y<s||x>e) return 0;
		return l->qry(x,y,a)+r->qry(x,y,a);
	}
};

int N,Q;
int A[MAX];
int B1[MAX],B2[MAX],B3[MAX];
map<int,int> m1;
map<int,int> m2;
map<int,int> m3;

int main(){
	ios::sync_with_stdio(false);cin.tie(NULL);
	cin>>N>>Q;
	for (int i=0;i<N;i++) cin>>A[i];
	for (int i=N-1;i>=0;i--){
		B1[i]=m1.find(A[i])==m1.end()?1<<30:m1[A[i]];
		B2[i]=m2.find(A[i])==m2.end()?1<<30:m2[A[i]];
		B3[i]=m3.find(A[i])==m3.end()?1<<30:m3[A[i]];
		if (m2.find(A[i])!=m2.end()) m3[A[i]]=m2[A[i]];
		if (m1.find(A[i])!=m1.end()) m2[A[i]]=m1[A[i]];
		m1[A[i]]=i;
	}
	auto st1=new ST(0,N-1,B1),st2=new ST(0,N-1,B2),st3=new ST(0,N-1,B3);
	while (Q--){
		int l,r;cin>>l>>r;l--,r--;
		cout<<2*st2->qry(l,r,r)-st1->qry(l,r,r)-st3->qry(l,r,r)<<'\n';
	}/**/
	
	/*
	for (int i=0;i<N;i++) cout<<B1[i]<<' ';cout<<'\n';
	for (int i=0;i<N;i++) cout<<B2[i]<<' ';cout<<'\n';
	for (int i=0;i<N;i++) cout<<B3[i]<<' ';cout<<'\n';
	*/
}

• Subtask 1: 140 / 140