oj.uz

Submission #912821

# Submission time Handle Problem Language Result Execution time Memory
912821 2024-01-20T01:17:38 Z NK_ Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 636 ms 40632 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

#define f first
#define s second
#define mp make_pair
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using vi = V<int>;

const int INF = 1e9;

struct BIT {
	vi A; int N; void init(int n) { N = n; A = vi(N, 0); }
	void upd(int p, int x) { for(++p;p<=N;p+=p&-p) A[p - 1] += x; }
	int sum(int r) { int s = 0; for(;r;r-=r&-r) s += A[r - 1]; return s; }
	int sum(int l, int r) { return sum(r + 1) - sum(l); }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
		
	int N, Q; cin >> N >> Q;
	
	vi A(N); for(auto& x : A) { cin >> x; --x; }

	vi pos(N), nxt(N), mx(N), stk = {N};
	for(int i = 0; i < N; i++) pos[A[i]] = i;

	for(int i = 0; i < N / 2; i++) mx[i] = max(A[i], i != 0 ? mx[i - 1] : -INF); // first half
	for(int i = N / 2; i < N; i++) mx[i] = max(A[i], i != N / 2 ? mx[i - 1] : -INF); // second half

	for(int i = N - 1; i >= 0; i--) {
		while(stk.back() != N && A[stk.back()] < A[i]) stk.pop_back();
		nxt[i] = stk.back();
		stk.pb(i);
	}

	V<AR<int, 3>> qry; vi ans(Q);
	for(int q = 0; q < Q; q++) {
		int t, i; cin >> t >> i; --i;
		if (t) qry.pb(AR<int, 3>{t, i, q});
		else ans[q] = A[i] + 1;
	}

	Q = sz(qry);

	BIT B; B.init(N);
	for(int i = 0; i < N; i++) B.upd(mx[i], 1);


	auto find = [&](int x) {
		int lo = 0, hi = N - 1; 
		while(lo < hi) {
			int mid = (lo + hi) / 2;
			if (B.sum(0, mid) >= x) hi = mid;
			else lo = mid + 1;
		}
		return lo;
	};

	auto answer = [&](int x, int i) {
		int rep = find(x + 1);
		int idx = pos[rep] + (x - B.sum(0, rep - 1));
		ans[i] = A[idx] + 1;
	};

	sort(begin(qry), end(qry));

	int t = 1, q = 0;
	while(q < Q) {

		// cout << t << endl;
		// for(int i = 0; i < N; i++) cout << i << " => " << B.sum(i, i) << endl;
		// cout << endl;

		while(q < Q && qry[q][0] <= t) {
			answer(qry[q][1], qry[q][2]); q++;
		} 

		int mid = find(N / 2); 
		int ex = B.sum(0, mid) - N / 2, bnd = pos[mid] + B.sum(mid, mid); B.upd(mid, -ex);

		if (ex == 0) {
			t = INF; continue;
		}

		int x = pos[mid] + B.sum(mid, mid); 
		while(x < bnd) {
			int nxtx = min(nxt[x], bnd);
			int amt = nxtx - x; B.upd(A[x], amt);
			x = nxtx;
		}

		++t;
	}

	for(auto& x : ans) cout << x << nl;

	exit(0-0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 20152 KB Output is correct
2 Correct 371 ms 27312 KB Output is correct
3 Correct 354 ms 27308 KB Output is correct
4 Correct 348 ms 25572 KB Output is correct
5 Correct 381 ms 27052 KB Output is correct
6 Correct 358 ms 25596 KB Output is correct
7 Correct 379 ms 27088 KB Output is correct
8 Correct 363 ms 26292 KB Output is correct
9 Correct 356 ms 25552 KB Output is correct
10 Correct 362 ms 25964 KB Output is correct
11 Correct 373 ms 26144 KB Output is correct
12 Correct 333 ms 23216 KB Output is correct
13 Correct 350 ms 26032 KB Output is correct
14 Correct 371 ms 26800 KB Output is correct
15 Correct 374 ms 25928 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 128 ms 13692 KB Output is correct
18 Correct 246 ms 19900 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 26592 KB Output is correct
2 Correct 495 ms 40632 KB Output is correct
3 Correct 436 ms 34040 KB Output is correct
4 Correct 474 ms 33700 KB Output is correct
5 Correct 473 ms 34600 KB Output is correct
6 Correct 454 ms 33536 KB Output is correct
7 Correct 487 ms 40032 KB Output is correct
8 Correct 469 ms 38576 KB Output is correct
9 Correct 440 ms 34420 KB Output is correct
10 Correct 487 ms 36804 KB Output is correct
11 Correct 412 ms 32860 KB Output is correct
12 Correct 427 ms 31160 KB Output is correct
13 Correct 501 ms 36712 KB Output is correct
14 Correct 421 ms 32428 KB Output is correct
15 Correct 501 ms 38568 KB Output is correct
16 Correct 18 ms 5456 KB Output is correct
17 Correct 163 ms 23964 KB Output is correct
18 Correct 398 ms 29632 KB Output is correct
19 Correct 49 ms 9188 KB Output is correct
20 Correct 113 ms 12736 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4548 KB Output is correct
2 Correct 69 ms 6496 KB Output is correct
3 Correct 71 ms 6220 KB Output is correct
4 Correct 60 ms 5828 KB Output is correct
5 Correct 70 ms 6208 KB Output is correct
6 Correct 60 ms 5936 KB Output is correct
7 Correct 61 ms 6212 KB Output is correct
8 Correct 69 ms 5960 KB Output is correct
9 Correct 63 ms 6088 KB Output is correct
10 Correct 54 ms 5836 KB Output is correct
11 Correct 53 ms 5976 KB Output is correct
12 Correct 63 ms 5828 KB Output is correct
13 Correct 56 ms 5828 KB Output is correct
14 Correct 54 ms 5832 KB Output is correct
15 Correct 68 ms 5832 KB Output is correct
16 Correct 9 ms 2908 KB Output is correct
17 Correct 23 ms 5040 KB Output is correct
18 Correct 37 ms 5128 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 20152 KB Output is correct
2 Correct 371 ms 27312 KB Output is correct
3 Correct 354 ms 27308 KB Output is correct
4 Correct 348 ms 25572 KB Output is correct
5 Correct 381 ms 27052 KB Output is correct
6 Correct 358 ms 25596 KB Output is correct
7 Correct 379 ms 27088 KB Output is correct
8 Correct 363 ms 26292 KB Output is correct
9 Correct 356 ms 25552 KB Output is correct
10 Correct 362 ms 25964 KB Output is correct
11 Correct 373 ms 26144 KB Output is correct
12 Correct 333 ms 23216 KB Output is correct
13 Correct 350 ms 26032 KB Output is correct
14 Correct 371 ms 26800 KB Output is correct
15 Correct 374 ms 25928 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 128 ms 13692 KB Output is correct
18 Correct 246 ms 19900 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 543 ms 26592 KB Output is correct
22 Correct 495 ms 40632 KB Output is correct
23 Correct 436 ms 34040 KB Output is correct
24 Correct 474 ms 33700 KB Output is correct
25 Correct 473 ms 34600 KB Output is correct
26 Correct 454 ms 33536 KB Output is correct
27 Correct 487 ms 40032 KB Output is correct
28 Correct 469 ms 38576 KB Output is correct
29 Correct 440 ms 34420 KB Output is correct
30 Correct 487 ms 36804 KB Output is correct
31 Correct 412 ms 32860 KB Output is correct
32 Correct 427 ms 31160 KB Output is correct
33 Correct 501 ms 36712 KB Output is correct
34 Correct 421 ms 32428 KB Output is correct
35 Correct 501 ms 38568 KB Output is correct
36 Correct 18 ms 5456 KB Output is correct
37 Correct 163 ms 23964 KB Output is correct
38 Correct 398 ms 29632 KB Output is correct
39 Correct 49 ms 9188 KB Output is correct
40 Correct 113 ms 12736 KB Output is correct
41 Correct 88 ms 4548 KB Output is correct
42 Correct 69 ms 6496 KB Output is correct
43 Correct 71 ms 6220 KB Output is correct
44 Correct 60 ms 5828 KB Output is correct
45 Correct 70 ms 6208 KB Output is correct
46 Correct 60 ms 5936 KB Output is correct
47 Correct 61 ms 6212 KB Output is correct
48 Correct 69 ms 5960 KB Output is correct
49 Correct 63 ms 6088 KB Output is correct
50 Correct 54 ms 5836 KB Output is correct
51 Correct 53 ms 5976 KB Output is correct
52 Correct 63 ms 5828 KB Output is correct
53 Correct 56 ms 5828 KB Output is correct
54 Correct 54 ms 5832 KB Output is correct
55 Correct 68 ms 5832 KB Output is correct
56 Correct 9 ms 2908 KB Output is correct
57 Correct 23 ms 5040 KB Output is correct
58 Correct 37 ms 5128 KB Output is correct
59 Correct 0 ms 344 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 636 ms 40616 KB Output is correct
62 Correct 626 ms 40376 KB Output is correct
63 Correct 600 ms 38548 KB Output is correct
64 Correct 584 ms 38336 KB Output is correct
65 Correct 609 ms 39928 KB Output is correct
66 Correct 626 ms 38532 KB Output is correct
67 Correct 549 ms 39060 KB Output is correct
68 Correct 545 ms 38396 KB Output is correct
69 Correct 539 ms 38068 KB Output is correct
70 Correct 545 ms 37372 KB Output is correct
71 Correct 527 ms 37052 KB Output is correct
72 Correct 544 ms 37804 KB Output is correct
73 Correct 540 ms 37720 KB Output is correct
74 Correct 529 ms 38000 KB Output is correct
75 Correct 565 ms 38056 KB Output is correct
76 Correct 18 ms 5560 KB Output is correct
77 Correct 173 ms 24344 KB Output is correct
78 Correct 350 ms 29000 KB Output is correct
79 Correct 1 ms 348 KB Output is correct
80 Correct 0 ms 348 KB Output is correct