oj.uz

Submission #1106391

# Submission time Handle Problem Language Result Execution time Memory
1106391 2024-10-30T08:55:41 Z stdfloat Simple game (IZhO17_game) C++17
49 / 100
 1000 ms 11596 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>

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

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;
		}
	};

	int z = 0;
	indexed_set s;
	for (auto i : a)
		s.insert({i, z++});

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

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

			upd(x, -1);
			s.erase(s.lower_bound({a[x], -1}));
			a[x] = vl;
			upd(x, 1);
			s.insert({vl, z++});
		}
		else {
			if (x > (*s.rbegin()).ff) {
				cout << "0\n"; continue;
			}

			pii y = *s.upper_bound({x, -1});
			cout << ((n - s.order_of_key(y) - cnt[y.ff]) << 1) - (x < a[0]) - (x < a[n - 1]) << '\n';
		}
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4176 KB Output is correct
2 Correct 254 ms 4432 KB Output is correct
3 Correct 247 ms 4432 KB Output is correct
4 Correct 241 ms 4432 KB Output is correct
5 Correct 244 ms 4432 KB Output is correct
6 Correct 248 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4176 KB Output is correct
2 Correct 254 ms 4432 KB Output is correct
3 Correct 247 ms 4432 KB Output is correct
4 Correct 241 ms 4432 KB Output is correct
5 Correct 244 ms 4432 KB Output is correct
6 Correct 248 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 51 ms 11176 KB Output is correct
9 Correct 94 ms 11364 KB Output is correct
10 Correct 99 ms 11576 KB Output is correct
11 Correct 39 ms 11080 KB Output is correct
12 Correct 82 ms 11596 KB Output is correct
13 Correct 92 ms 11592 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4176 KB Output is correct
2 Correct 254 ms 4432 KB Output is correct
3 Correct 247 ms 4432 KB Output is correct
4 Correct 241 ms 4432 KB Output is correct
5 Correct 244 ms 4432 KB Output is correct
6 Correct 248 ms 4432 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 51 ms 11176 KB Output is correct
9 Correct 94 ms 11364 KB Output is correct
10 Correct 99 ms 11576 KB Output is correct
11 Correct 39 ms 11080 KB Output is correct
12 Correct 82 ms 11596 KB Output is correct
13 Correct 92 ms 11592 KB Output is correct
14 Execution timed out 1070 ms 11024 KB Time limit exceeded
15 Halted 0 ms 0 KB -