Submission #1106391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106391		stdfloat	Simple game (IZhO17_game)	C++17	49 / 100	1070 ms	11596 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 0 / 51