oj.uz

Submission #754817

# Submission time Handle Problem Language Result Execution time Memory
754817 2023-06-08T16:40:30 Z raysh07 Index (COCI21_index) C++17
110 / 110
 2307 ms 112440 KB 
#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.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10068 KB Output is correct
2 Correct 9 ms 9940 KB Output is correct
3 Correct 10 ms 10068 KB Output is correct
4 Correct 9 ms 10068 KB Output is correct
5 Correct 9 ms 10068 KB Output is correct
6 Correct 9 ms 9940 KB Output is correct
7 Correct 9 ms 9940 KB Output is correct
8 Correct 9 ms 9976 KB Output is correct
9 Correct 9 ms 10068 KB Output is correct
10 Correct 9 ms 10068 KB Output is correct
11 Correct 437 ms 31996 KB Output is correct
12 Correct 438 ms 31920 KB Output is correct
13 Correct 438 ms 32188 KB Output is correct
14 Correct 525 ms 31960 KB Output is correct
15 Correct 477 ms 31916 KB Output is correct
16 Correct 432 ms 32012 KB Output is correct
17 Correct 441 ms 32384 KB Output is correct
18 Correct 481 ms 32060 KB Output is correct
19 Correct 426 ms 32188 KB Output is correct
20 Correct 422 ms 31928 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10068 KB Output is correct
2 Correct 9 ms 9940 KB Output is correct
3 Correct 10 ms 10068 KB Output is correct
4 Correct 9 ms 10068 KB Output is correct
5 Correct 9 ms 10068 KB Output is correct
6 Correct 9 ms 9940 KB Output is correct
7 Correct 9 ms 9940 KB Output is correct
8 Correct 9 ms 9976 KB Output is correct
9 Correct 9 ms 10068 KB Output is correct
10 Correct 9 ms 10068 KB Output is correct
11 Correct 437 ms 31996 KB Output is correct
12 Correct 438 ms 31920 KB Output is correct
13 Correct 438 ms 32188 KB Output is correct
14 Correct 525 ms 31960 KB Output is correct
15 Correct 477 ms 31916 KB Output is correct
16 Correct 432 ms 32012 KB Output is correct
17 Correct 441 ms 32384 KB Output is correct
18 Correct 481 ms 32060 KB Output is correct
19 Correct 426 ms 32188 KB Output is correct
20 Correct 422 ms 31928 KB Output is correct
21 Correct 2273 ms 107404 KB Output is correct
22 Correct 2136 ms 107136 KB Output is correct
23 Correct 2136 ms 108408 KB Output is correct
24 Correct 2218 ms 108644 KB Output is correct
25 Correct 2036 ms 108020 KB Output is correct
26 Correct 2117 ms 107368 KB Output is correct
27 Correct 2307 ms 107416 KB Output is correct
28 Correct 2231 ms 111952 KB Output is correct
29 Correct 2225 ms 110384 KB Output is correct
30 Correct 2269 ms 112440 KB Output is correct