oj.uz

Submission #1106394

# Submission time Handle Problem Language Result Execution time Memory
1106394 2024-10-30T09:03:37 Z stdfloat Simple game (IZhO17_game) C++17
49 / 100
 1000 ms 13896 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;

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;

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

	auto upd = [&](int x, int vl) {
		if (0 < x) {
			for (int i = min(a[x], a[x - 1]); i > 0; i--)
				cnt[i] += vl;
		}
		if (x + 1 < n) {
			for (int i = min(a[x], a[x + 1]); i > 0; i--)
				cnt[i] += 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--;

			upd(x, -1);
			updfn(a[x], -1);
			s.erase(s.find(a[x]));
			
			a[x] = vl;
			
			upd(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 - cnt[y]) << 1) - (x < a[0]) - (x < a[n - 1]) << '\n';
		}
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8272 KB Output is correct
2 Correct 270 ms 8272 KB Output is correct
3 Correct 261 ms 8272 KB Output is correct
4 Correct 249 ms 8272 KB Output is correct
5 Correct 247 ms 8272 KB Output is correct
6 Correct 248 ms 8272 KB Output is correct
7 Correct 4 ms 8272 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8272 KB Output is correct
2 Correct 270 ms 8272 KB Output is correct
3 Correct 261 ms 8272 KB Output is correct
4 Correct 249 ms 8272 KB Output is correct
5 Correct 247 ms 8272 KB Output is correct
6 Correct 248 ms 8272 KB Output is correct
7 Correct 4 ms 8272 KB Output is correct
8 Correct 38 ms 13392 KB Output is correct
9 Correct 78 ms 13764 KB Output is correct
10 Correct 74 ms 13896 KB Output is correct
11 Correct 34 ms 13384 KB Output is correct
12 Correct 62 ms 13896 KB Output is correct
13 Correct 54 ms 13896 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8272 KB Output is correct
2 Correct 270 ms 8272 KB Output is correct
3 Correct 261 ms 8272 KB Output is correct
4 Correct 249 ms 8272 KB Output is correct
5 Correct 247 ms 8272 KB Output is correct
6 Correct 248 ms 8272 KB Output is correct
7 Correct 4 ms 8272 KB Output is correct
8 Correct 38 ms 13392 KB Output is correct
9 Correct 78 ms 13764 KB Output is correct
10 Correct 74 ms 13896 KB Output is correct
11 Correct 34 ms 13384 KB Output is correct
12 Correct 62 ms 13896 KB Output is correct
13 Correct 54 ms 13896 KB Output is correct
14 Execution timed out 1057 ms 13376 KB Time limit exceeded
15 Halted 0 ms 0 KB -