oj.uz

Submission #1106404

# Submission time Handle Problem Language Result Execution time Memory
1106404 2024-10-30T09:22:20 Z stdfloat Simple game (IZhO17_game) C++17
100 / 100
 669 ms 42832 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define sz(a)	(int)(a).size()
#define all(a)	(a).begin(), (a).end()

#define ff	first
#define ss	second
#define pii	pair<int, int>

const int N = (int)1e6 + 1;

vector<int> st(N << 2), lz(N << 2);

void LZ(int nd, int l, int r) {
	st[nd] += lz[nd];

	if (l != r) {
		int ch = (nd << 1) + 1;
		lz[ch] += lz[nd]; lz[ch + 1] += lz[nd];
	}

	lz[nd] = 0;
}

int upd(int nd, int l, int r, int x, int y, int vl) {
	LZ(nd, l, r);

	if (r < x || y < l) return st[nd];

	if (x <= l && r <= y) {
		lz[nd] += vl; LZ(nd, l, r);
		return st[nd];
	}

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return st[nd] = max(upd(ch, l, md, x, y, vl), upd(ch + 1, md + 1, r, x, y, vl));
}

int fnd(int nd, int l, int r, int x) {
	LZ(nd, l, r);

	if (r < x || x < l) return 0;

	if (l == r) return st[nd];

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return max(fnd(ch, l, md, x), fnd(ch + 1, md + 1, r, x));
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	vector<int> a(n);
	for (auto &i : a)
		cin >> i;

	for (int i = 0; i + 1 < n; i++)
		upd(0, 1, N - 1, min(a[i], a[i + 1]), min(a[i], a[i + 1]), 1);
	for (int i = N - 2; i >= 0; i--)
		upd(0, 1, N - 1, i, i, fnd(0, 1, N - 1, i + 1));

	auto updz = [&](int x, int vl) {
		if (0 < x) upd(0, 1, N - 1, 1, min(a[x], a[x - 1]), vl);
		if (x + 1 < n) upd(0, 1, N - 1, 1, min(a[x], a[x + 1]), vl);
	};

	vector<int> fn(N);
	auto updfn = [&](int x, int vl) {
		for (; x < N; x += x & -x)
			fn[x] += vl;
	};

	multiset<int> s;
	for (int i = 0; i < n; i++) {
		updfn(a[i], 1);
		s.insert(a[i]);
	}

	while (q--) {
		int tp, x;
		cin >> tp >> x;

		if (tp == 1) {
			int vl;
			cin >> vl; x--;

			updz(x, -1);
			updfn(a[x], -1);
			s.erase(s.find(a[x]));
			
			a[x] = vl;
			
			updz(x, 1);
			updfn(a[x], 1);
			s.insert(vl);
		}
		else {
			if (x > *s.rbegin()) {
				cout << "0\n"; continue;
			}

			int y = *s.upper_bound(x), z = 0;
			for (int i = y - 1; i > 0; i -= i & -i)
				z += fn[i];

			cout << ((n - z - fnd(0, 1, N - 1, y)) << 1) - (x < a[0]) - (x < a[n - 1]) << '\n';
		}
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 35656 KB Output is correct
2 Correct 415 ms 35664 KB Output is correct
3 Correct 471 ms 35616 KB Output is correct
4 Correct 434 ms 35656 KB Output is correct
5 Correct 418 ms 35656 KB Output is correct
6 Correct 447 ms 35656 KB Output is correct
7 Correct 452 ms 35616 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 35656 KB Output is correct
2 Correct 415 ms 35664 KB Output is correct
3 Correct 471 ms 35616 KB Output is correct
4 Correct 434 ms 35656 KB Output is correct
5 Correct 418 ms 35656 KB Output is correct
6 Correct 447 ms 35656 KB Output is correct
7 Correct 452 ms 35616 KB Output is correct
8 Correct 532 ms 40868 KB Output is correct
9 Correct 569 ms 41288 KB Output is correct
10 Correct 574 ms 41292 KB Output is correct
11 Correct 488 ms 41032 KB Output is correct
12 Correct 537 ms 41124 KB Output is correct
13 Correct 545 ms 41128 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 35656 KB Output is correct
2 Correct 415 ms 35664 KB Output is correct
3 Correct 471 ms 35616 KB Output is correct
4 Correct 434 ms 35656 KB Output is correct
5 Correct 418 ms 35656 KB Output is correct
6 Correct 447 ms 35656 KB Output is correct
7 Correct 452 ms 35616 KB Output is correct
8 Correct 532 ms 40868 KB Output is correct
9 Correct 569 ms 41288 KB Output is correct
10 Correct 574 ms 41292 KB Output is correct
11 Correct 488 ms 41032 KB Output is correct
12 Correct 537 ms 41124 KB Output is correct
13 Correct 545 ms 41128 KB Output is correct
14 Correct 644 ms 40836 KB Output is correct
15 Correct 652 ms 42824 KB Output is correct
16 Correct 669 ms 42768 KB Output is correct
17 Correct 639 ms 42768 KB Output is correct
18 Correct 629 ms 42832 KB Output is correct