oj.uz

Submission #1107044

# Submission time Handle Problem Language Result Execution time Memory
1107044 2024-10-31T12:58:45 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 1700 ms 62160 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8492 KB Output is correct
2 Correct 10 ms 8476 KB Output is correct
3 Correct 10 ms 8660 KB Output is correct
4 Correct 11 ms 8504 KB Output is correct
5 Correct 10 ms 8488 KB Output is correct
6 Correct 10 ms 8492 KB Output is correct
7 Correct 11 ms 8492 KB Output is correct
8 Correct 10 ms 8492 KB Output is correct
9 Correct 12 ms 8456 KB Output is correct
10 Correct 10 ms 8660 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8492 KB Output is correct
2 Correct 10 ms 8476 KB Output is correct
3 Correct 10 ms 8660 KB Output is correct
4 Correct 11 ms 8504 KB Output is correct
5 Correct 10 ms 8488 KB Output is correct
6 Correct 10 ms 8492 KB Output is correct
7 Correct 11 ms 8492 KB Output is correct
8 Correct 10 ms 8492 KB Output is correct
9 Correct 12 ms 8456 KB Output is correct
10 Correct 10 ms 8660 KB Output is correct
11 Correct 328 ms 30480 KB Output is correct
12 Correct 338 ms 30404 KB Output is correct
13 Correct 316 ms 30444 KB Output is correct
14 Correct 321 ms 30480 KB Output is correct
15 Correct 322 ms 30388 KB Output is correct
16 Correct 302 ms 30480 KB Output is correct
17 Correct 297 ms 30480 KB Output is correct
18 Correct 309 ms 30472 KB Output is correct
19 Correct 297 ms 30468 KB Output is correct
20 Correct 303 ms 30480 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8492 KB Output is correct
2 Correct 10 ms 8476 KB Output is correct
3 Correct 10 ms 8660 KB Output is correct
4 Correct 11 ms 8504 KB Output is correct
5 Correct 10 ms 8488 KB Output is correct
6 Correct 10 ms 8492 KB Output is correct
7 Correct 11 ms 8492 KB Output is correct
8 Correct 10 ms 8492 KB Output is correct
9 Correct 12 ms 8456 KB Output is correct
10 Correct 10 ms 8660 KB Output is correct
11 Correct 328 ms 30480 KB Output is correct
12 Correct 338 ms 30404 KB Output is correct
13 Correct 316 ms 30444 KB Output is correct
14 Correct 321 ms 30480 KB Output is correct
15 Correct 322 ms 30388 KB Output is correct
16 Correct 302 ms 30480 KB Output is correct
17 Correct 297 ms 30480 KB Output is correct
18 Correct 309 ms 30472 KB Output is correct
19 Correct 297 ms 30468 KB Output is correct
20 Correct 303 ms 30480 KB Output is correct
21 Correct 1588 ms 62012 KB Output is correct
22 Correct 1648 ms 62032 KB Output is correct
23 Correct 1598 ms 61964 KB Output is correct
24 Correct 1631 ms 62020 KB Output is correct
25 Correct 1700 ms 62068 KB Output is correct
26 Correct 1588 ms 61960 KB Output is correct
27 Correct 1576 ms 62160 KB Output is correct
28 Correct 1618 ms 61952 KB Output is correct
29 Correct 1616 ms 62056 KB Output is correct
30 Correct 1534 ms 61960 KB Output is correct