Submission #937153

#	Time	Username	Problem	Language	Result	Execution time	Memory
937153		goduadzesaba	Index (COCI21_index)	C++17	110 / 110	705 ms	42528 KiB

index

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,a[N],ans[N],l[N],x[N],y[N],r[N],m[N],tree[N]; 
vector <int> v[N],que[N];
void update(int idx,int val){
	for (int i=idx; i<N; i+=i&(-i)) {
		tree[i]+=val;
	}
}
int get(int idx) {
	int ans=0;
	for (int i=idx; i>0; i-=i&(-i)) {
		ans+=tree[i];
	}
	return ans;
}
int main() {
	cin>>n>>q;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
		v[a[i]].push_back(i);
	}
	for (int i=1; i<=q; i++){
		cin>>x[i]>>y[i];
		l[i]=1; r[i]=200000; m[i]=(l[i]+r[i])/2;
	}
	while(true){
		int check=0;
		for (int i=1; i<=q; i++){
			if (l[i]>r[i]) continue;
			//cout<<l[i]<<" "<<r[i]<<endl;
			check=1;
			que[m[i]].push_back(i);
		}
		if(!check) break;
		for (int h=2e5; h>0; h--){
			for (int j:v[h]) {
				update(j, 1);
			//	cout<<h<<" "<<j<<" -------- > "<<1<<endl;
			}
			for (int j:que[h]){
				if(get(y[j])-get(x[j]-1)>=h){ // get(x[j], y[j])
					ans[j]=m[j]; l[j]=m[j]+1; 
				}
				else r[j]=m[j]-1; 

				m[j] = (l[j]+r[j])/2;
			}
		}
		for (int i=1; i<=2e5; i++) {
			for (int j:v[i]) {
				update(j, -1);
			}
			que[i].clear();
		}
	}
	for (int i=1; i<=q; i++) cout<<ans[i]<<'\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50