oj.uz

Submission #1048389

# Submission time Handle Problem Language Result Execution time Memory
1048389 2024-08-08T07:15:16 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 1190 ms 138020 KB 
#include<bits/stdc++.h>
using namespace std;
const int nMax = 2e5 + 7;
vector < long long > ar;
struct Node{
	Node* left;
	Node* right;
	long long val;
	Node(){
		left = NULL;
		right = NULL;
		val = 0;
	}
	Node(Node* a){
		left = a -> left;
		right = a -> right;
		val = a -> val;
	}
};

vector <Node*> roots;

void build(long long l , long long r , Node* nd){
	if(l > r){
		return;
	}
	if(l == r){
		nd -> val = 0;
		return;
	}

	nd -> right = new Node();
	nd -> left = new Node();
	long long m = (l + r) / 2;
	build(l , m , nd -> left);
	build(m + 1 , r , nd -> right);
	nd -> val = 0;
}
void update(long long l , long long r , long long f , long long valu , Node* nd){
//	cout << l << " " << r;
	if(nd == NULL || l > r || l > f || f > r){
		return;
	}
	if(l == r){
		nd -> val += valu;
		return;
	}
	long long m = (l + r) / 2;
	if(l <= f && f <= m){
		nd -> left = new Node(nd -> left);
	}
	else{
		nd -> right = new Node(nd -> right);
	}
	update(l , m , f , valu , nd -> left);
	update(m + 1 , r , f , valu , nd -> right);
	nd -> val = (nd -> right -> val) + (nd -> left -> val);
}
long long search(long long l , long long r , long long fl, long long fr ,  Node* nd){
	if(l > r || l > fr || fl > r){
		return 0;
	}
	if(fl <= l && r <= fr){
		return nd -> val;
	}
	long long m = (l + r) / 2;
		return search(l , m , fl , fr , nd -> left) + search(m + 1 , r , fl , fr , nd -> right);

}
int main(){
	long long n , q , k , x , mx;
	mx = 0;
	cin >> n >> q;
	for(long long i = 1; n >= i; i++){
		cin >> x;
		mx = max(mx , x);
		ar.push_back(x);

	}

	Node* tmp;
	tmp = new Node();
	
	build(1 , mx , tmp);
	roots.push_back(tmp);
	for(long long i = 1; n >= i; i++){
		x = ar[i - 1];

		tmp = new Node(roots[i - 1]);
		update(1 , mx , x , 1 ,tmp);
		roots.push_back(tmp);

	}
	for(long long i = 0; q > i; i++){
		cin >> k >> x;
		long long l = 1 , r = mx;
		while(r > l){
			//cout << l << " " << r <<"\n";
			long long m = ((l + r) + 1) / 2;
			if((search(1 , mx , m , mx , roots[x]) - search(1 , mx , m , mx , roots[k - 1])) >= m){
				l = m;
			}
			else{
				r = m - 1;
			}
		}
		cout << l << "\n";
	}
	

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 172 ms 31396 KB Output is correct
12 Correct 221 ms 31432 KB Output is correct
13 Correct 205 ms 31412 KB Output is correct
14 Correct 172 ms 31516 KB Output is correct
15 Correct 186 ms 31436 KB Output is correct
16 Correct 223 ms 31432 KB Output is correct
17 Correct 221 ms 31436 KB Output is correct
18 Correct 199 ms 31488 KB Output is correct
19 Correct 184 ms 31548 KB Output is correct
20 Correct 173 ms 31564 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 172 ms 31396 KB Output is correct
12 Correct 221 ms 31432 KB Output is correct
13 Correct 205 ms 31412 KB Output is correct
14 Correct 172 ms 31516 KB Output is correct
15 Correct 186 ms 31436 KB Output is correct
16 Correct 223 ms 31432 KB Output is correct
17 Correct 221 ms 31436 KB Output is correct
18 Correct 199 ms 31488 KB Output is correct
19 Correct 184 ms 31548 KB Output is correct
20 Correct 173 ms 31564 KB Output is correct
21 Correct 1190 ms 137876 KB Output is correct
22 Correct 940 ms 137812 KB Output is correct
23 Correct 939 ms 137788 KB Output is correct
24 Correct 969 ms 137920 KB Output is correct
25 Correct 1018 ms 138008 KB Output is correct
26 Correct 981 ms 137832 KB Output is correct
27 Correct 1033 ms 137836 KB Output is correct
28 Correct 1113 ms 138020 KB Output is correct
29 Correct 1059 ms 137776 KB Output is correct
30 Correct 1059 ms 138016 KB Output is correct