Submission #1048389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048389		vjudge1	Index (COCI21_index)	C++17	110 / 110	1190 ms	138020 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50