oj.uz

답안 #754815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
754815 2023-06-08T16:39:38 Z raysh07 Index (COCI21_index) C++17
60 / 110
 2500 ms 203336 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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10316 KB Output is correct
2 Correct 10 ms 10384 KB Output is correct
3 Correct 9 ms 10324 KB Output is correct
4 Correct 12 ms 10324 KB Output is correct
5 Correct 9 ms 10256 KB Output is correct
6 Correct 9 ms 10252 KB Output is correct
7 Correct 9 ms 10324 KB Output is correct
8 Correct 9 ms 10324 KB Output is correct
9 Correct 11 ms 10324 KB Output is correct
10 Correct 9 ms 10384 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10316 KB Output is correct
2 Correct 10 ms 10384 KB Output is correct
3 Correct 9 ms 10324 KB Output is correct
4 Correct 12 ms 10324 KB Output is correct
5 Correct 9 ms 10256 KB Output is correct
6 Correct 9 ms 10252 KB Output is correct
7 Correct 9 ms 10324 KB Output is correct
8 Correct 9 ms 10324 KB Output is correct
9 Correct 11 ms 10324 KB Output is correct
10 Correct 9 ms 10384 KB Output is correct
11 Correct 512 ms 52948 KB Output is correct
12 Correct 438 ms 53820 KB Output is correct
13 Correct 438 ms 53144 KB Output is correct
14 Correct 441 ms 53820 KB Output is correct
15 Correct 455 ms 53268 KB Output is correct
16 Correct 458 ms 52980 KB Output is correct
17 Correct 439 ms 53788 KB Output is correct
18 Correct 491 ms 53740 KB Output is correct
19 Correct 436 ms 53552 KB Output is correct
20 Correct 461 ms 53044 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10316 KB Output is correct
2 Correct 10 ms 10384 KB Output is correct
3 Correct 9 ms 10324 KB Output is correct
4 Correct 12 ms 10324 KB Output is correct
5 Correct 9 ms 10256 KB Output is correct
6 Correct 9 ms 10252 KB Output is correct
7 Correct 9 ms 10324 KB Output is correct
8 Correct 9 ms 10324 KB Output is correct
9 Correct 11 ms 10324 KB Output is correct
10 Correct 9 ms 10384 KB Output is correct
11 Correct 512 ms 52948 KB Output is correct
12 Correct 438 ms 53820 KB Output is correct
13 Correct 438 ms 53144 KB Output is correct
14 Correct 441 ms 53820 KB Output is correct
15 Correct 455 ms 53268 KB Output is correct
16 Correct 458 ms 52980 KB Output is correct
17 Correct 439 ms 53788 KB Output is correct
18 Correct 491 ms 53740 KB Output is correct
19 Correct 436 ms 53552 KB Output is correct
20 Correct 461 ms 53044 KB Output is correct
21 Correct 2281 ms 203336 KB Output is correct
22 Correct 2451 ms 201932 KB Output is correct
23 Correct 2284 ms 202676 KB Output is correct
24 Correct 2434 ms 200244 KB Output is correct
25 Correct 2268 ms 202288 KB Output is correct
26 Correct 2289 ms 202684 KB Output is correct
27 Execution timed out 2553 ms 200344 KB Time limit exceeded
28 Halted 0 ms 0 KB -