Submission #1300409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300409		ghostlywalrus	Index (COCI21_index)	C++20	110 / 110	352 ms	98740 KiB

index

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define int long long
#define PI pair<int,int>
#define f first
#define s second
#define pb push_back
#define szo(x) ((int)x.size())

const int MAX = 2e7;
int seg[MAX];
int L[MAX], R[MAX];
int nodes = 1;

const int LIM = 2e5+10;

void build(int x = 1, int l = 0, int r = LIM){
	 if (l == r) return;
	 int tm = (l+r)/2;
	 L[x] = nodes++, R[x] = nodes++;
	 build(L[x], l, tm); build(R[x], tm+1, r);
}

int update(int id, int val, int x, int xo, int l = 0, int r = LIM){
	if (l == r) return seg[x] = seg[xo]+val;
	int tm = (l+r)/2;
	if (id <= tm) return seg[x] = update(id, val, L[x] = nodes++, L[xo], l, tm) + seg[R[x] = R[xo]];
	return seg[x] = update(id, val, R[x] = nodes++, R[xo], tm+1, r) + seg[L[x] = L[xo]];
}

int solve(int r1, int r2, int acc, int l = 0, int r = LIM){
	if (l == r) return l;
	int tm = (l+r)/2;
	if (acc + seg[R[r1]] - seg[R[r2]] >= tm+1) return solve(R[r1], R[r2], acc, tm+1, r); 
	return solve(L[r1], L[r2], acc+seg[R[r1]]-seg[R[r2]], l, tm);
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
	int n,q; cin >> n >> q;
	vector<int> vec(n+1);
	for (int i = 1; i <= n; ++i) cin >> vec[i];

	build();
	vector<int> rts(n+1);
	rts[0] = 0;
	for (int i = 1; i <= n; ++i){
	 	rts[i] = nodes++;
		update(vec[i], 1, rts[i], rts[i-1]);
	}

	while (q--){
	 	int l, r; cin >> l >> r;
		cout << solve(rts[r], rts[l-1], 0) << '\n';
	}

    return 0;
}

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