Submission #1106404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106404		stdfloat	Simple game (IZhO17_game)	C++17	100 / 100	669 ms	42832 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;

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