Submission #1280045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280045		magomagrito	Index (COCI21_index)	C++20	60 / 110	276 ms	49044 KiB

index

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const int MAX = 2e5 + 10;
const int UPD = 2e5 + 10;
const int LOG = 18;
const int MAXS = 2 * MAX + UPD * LOG;

int cnt;
int seg[MAXS], L[MAXS], R[MAXS];

void build(int p, int l=0, int r=MAX-1){
	if(l == r) return void();
	L[p] = cnt++, R[p] = cnt++;
	int m = (l+r)/2;
	build(L[p], l, m); build(R[p], m+1, r);
}
void update(int i, int x, int np, int p, int l=0, int r=MAX-1){
	if(l == r) return void(seg[np] = seg[p] + x);
	int m = (l+r)/2;
	if(i <= m){
		L[np] = cnt++;
		R[np] = R[p];
		update(i, x, L[np], L[p], l, m);
	}
	else{
		L[np] = L[p];
		R[np] = cnt++;
		update(i, x, R[np], R[p], m+1, r);
	}
	seg[np] = seg[L[np]] + seg[R[np]];
}
int solve(int lp, int rp, int sum=0, int l=0, int r=MAX-1){
	if(seg[rp] - seg[lp] + sum < l) return -1;
	if(l == r) return l;
	int m = (l+r)/2;
	int x = solve(R[lp], R[rp], sum, m+1, r);
	if(x != -1) return x;
	sum += seg[R[rp]] - seg[R[lp]];
	return solve(L[lp], L[rp], sum, l, m);
}

int main() { _
	int n, q; cin >> n >> q;
	vector<int> a(n+1); for(int i=1; i<=n; i++) cin >> a[i];

	vector<int> vers(n+1);

	cnt = 1;
	build(0);
	vers[0] = 0;

	for(int i=1; i<=n; i++){
		int rt = cnt++;
		update(a[i], +1, rt, vers[i-1]);
		vers[i] = rt;
	}

	while(q--){
		int l, r; cin >> l >> r;
		cout << solve(vers[l-1], vers[r]) << endl;
	}
	exit(0);
}

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