Submission #754817

#	Time	Username	Problem	Language	Result	Execution time	Memory
754817		raysh07	Index (COCI21_index)	C++17	110 / 110	2307 ms	112440 KiB

index

#include <bits/stdc++.h>
using namespace std;
//#define int long long 
#define INF (int)(1e9)

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct Query{
	int x, y, l, r, i;
};

const int N = 2e5 + 69;
int a[N];
vector <Query> adj[N];
int n, q;
int ans[N];
int seg[4 * N];
vector <Query> all;
vector <int> vec[N];

void upd(int l, int r, int pos, int qp){
	seg[pos]++;
	if (l == r){
		return;
	}
	int mid = (l + r)/2;
	if (qp <= mid) upd(l, mid, pos*2, qp);
	else upd(mid + 1, r, pos*2 + 1, qp);
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

int query(int l, int r, int pos, int ql, int qr){
	if (l >= ql && r <= qr) return seg[pos];
	else if (l > qr || r < ql) return 0;

	int mid = (l + r)/2;
	return query(l, mid, pos*2, ql, qr) + query(mid + 1, r, pos*2 + 1, ql, qr);
}

void pbs(){
	all.clear();
	for (int i = 0; i <= n; i++){
		for (auto x : adj[i]){
			all.push_back(x);
		}
		adj[i].clear();
	}

	for (auto x : all){
		adj[(x.l + x.r + 1)/2].push_back(x);
	}

	for (int i = 0; i < 4 * n; i++){
		seg[i] = 0;
	}

	for (int i = n; i >= 0; i--){
		for (auto x : vec[i]){
			upd(1, n, 1, x);
		}

		for (auto &x : adj[i]){
			if (x.l == x.r) continue;
			int val = query(1, n, 1, x.x, x.y);

			//cout << x.x << " " << x.y << " " << val << " " << i << "\n";
			if (val >= i){
				x.l = i;
			} else {
				x.r = i - 1;
			}
		}
	}
}

void Solve(){
	cin >> n >> q;

	for (int i = 1; i <= n; i++){
		 cin >> a[i];
		 vec[a[i]].push_back(i);
	}

	for (int i = 1; i <= q; i++){
		int l, r; 
		cin >> l >> r;

		Query ok;
		ok.x = l;
		ok.y = r;
		ok.l = 0;
		ok.r = n;
		ok.i = i;
		adj[0].push_back(ok);
	}
	
	for (int it = 0; it < 20; it++){
		pbs();
	}

	for (int i = 0; i <= n; i++){
		for (auto x : adj[i]){
			ans[x.i] = x.l;
		}
	}
	
	for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t = 1; 
	//cin >> t;
	
	while (t--) Solve();
	return 0;
}

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