Submission #1107044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107044		vjudge1	Index (COCI21_index)	C++17	110 / 110	1700 ms	62160 KiB

index

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define fi first
#define se second
#define endl "\n"
//~ #define int long long

 
using namespace std;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
const int inf  = 1e9+7;
const int mod = 2019201997;
//~ const int mod2 = 999983;
typedef long long ll;

int n, q;
vector<int> lleft, rright, val, roots;
int newNode(){
	//~ cout<<lleft.size()<< "jakakjkja"<<endl;
	lleft.pb(-1);
	rright.pb(-1);
	val.pb(0);
	//~ cout<<lleft.size()<<" jajsjsjsajs"<<endl;
	return lleft.size()-1;
}

int newNode(int node){
	//~ cout<<lleft.size()<< "aajjakkjakja "<<node<<endl;
	lleft.pb(lleft[node]);
	rright.pb(rright[node]);
	val.pb(val[node]);
	return lleft.size()-1;
}

void update(int node, int l, int r, int u, int v){
	//~ cerr<<node<<" :: "<<l<<" :: "<<r<<" :: "<<u<<" :: "<<v<<endl;
	if(u<l || u>r)return;
	if(l==r){
		val[node]+=v;
		return;
	}
	
	int m = (l+r)/2;
	if(u<=m){
		if(lleft[node] == -1){
			//int t=newNode();
			lleft[node] = newNode();
			//~ cerr<<lleft[node]<<"llefelft"<<endl;
		}
		lleft[node] = newNode(lleft[node]);
		update(lleft[node], l, m, u, v);
	}
	
	else{
		//~ cout<<rright[node]<<endl;
		if(rright[node] == -1){
			//int t=newNode();
			rright[node] = newNode();
			//~ cout<<rright[node]<<"rrigtht"<<endl;
		}
		//~ cout<<rright[node]<<endl;
		rright[node] = newNode(rright[node]);
		update(rright[node], m+1, r, u, v);
	}
	val[node] = lleft[node]!=-1 ? val[lleft[node]] : 0;
	val[node] += rright[node]!=-1 ? val[rright[node]] : 0;
}

int query(int node, int l, int r, int s, int f){
	if(l>f || r<s)return 0;
	if(l>=s && r<=f)return val[node];
	int m = (l+r)/2;
	int t1 = lleft[node] != -1 ? query(lleft[node], l, m, s, f) : 0;
	int t2 = rright[node] != -1 ? query(rright[node], m+1, r, s, f) : 0;
	return t1+t2;
}

int32_t main(){
	fast;
	cin>>n>>q;
	int a[n+5];
	vector<vector<int>> v;
	v.assign(2e5+5, vector<int>());
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v[a[i]].pb(i);
	}
	
	roots.pb(newNode());
	//~ roots.pb(newNode()); 
	for(int i=1;i<=2e5;i++){
		roots.pb(newNode(roots.back()));
		for(auto it: v[i]){
			update(roots.back(), 1, n, it, 1);
		}
		//~ cerr<<"pitipiti"<<endl;
	}
	//~ cerr<<"pitipitti"<<endl;
	while(q--){
		int a, b;
		cin>>a>>b;
		int l = 1, r = 2e5;
		while(l<=r){
			int m = (l+r)/2;
			//~ cout<<query(roots.back(), 1, n, a, b)-query(roots[m], 1, n, a, b)<<" :: "<<l<<" :: "<<r<<" :: "<<m<<endl;
			if(query(roots.back(), 1, n, a, b)-(m>0 ? query(roots[m-1], 1, n, a, b) : 0)>=m){
				l=m+1;
			}
			else r=m-1;
		}
		
		cout<<r<<endl;
		//~ cout<<r<<" :: "<<query(roots.back(), 1, n, a, b)-query(roots[r], 1, n, a, b)<<endl;
	}	
}

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