Submission #1106394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106394		stdfloat	Simple game (IZhO17_game)	C++17	49 / 100	1057 ms	13896 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>

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