Submission #344841

#	Time	Username	Problem	Language	Result	Execution time	Memory
344841		SeDunion	Simple game (IZhO17_game)	C++17	100 / 100	125 ms	10860 KiB

game

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

int Mx[N], Mn[N];
void MxUpd(int pos, int val) {
	while (pos < N) {
		Mx[pos] += val;
		pos |= pos + 1;
	}
}
int MxGet(int pos) {
	int res = 0;
	while (pos >= 0) {
		res += Mx[pos];
		pos &= pos + 1, pos--;
	}
	return res;
}
void MnUpd(int pos, int val) {
	while (pos < N) {
		Mn[pos] += val;
		pos |= pos + 1;
	}
}
int MnGet(int pos) {
	int res = 0;
	while (pos >= 0) {
		res += Mn[pos];
		pos &= pos + 1, pos--;
	}
	return res;
}

int n, m, a[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1 ; i <= n ; ++ i) {
		cin >> a[i];
	}
	for (int i = 2 ; i <= n ; ++ i) {
		MxUpd(max(a[i], a[i - 1]), 1);
		MnUpd(min(a[i], a[i - 1]), 1);
	}
	for (int t, x, y ; m-- ; ) {
		cin >> t >> x;
		if (t == 1) {
			cin >> y;
			if (x > 1) MxUpd(max(a[x], a[x - 1]), -1), MnUpd(min(a[x], a[x - 1]), -1);
			if (x < n) MxUpd(max(a[x], a[x + 1]), -1), MnUpd(min(a[x], a[x + 1]), -1);
			a[x] = y;
			if (x > 1) MxUpd(max(a[x], a[x - 1]), +1), MnUpd(min(a[x], a[x - 1]), +1);
			if (x < n) MxUpd(max(a[x], a[x + 1]), +1), MnUpd(min(a[x], a[x + 1]), +1);
		} else {
			//cout << MxGet(N - 1) - MxGet(x) << " " << MnGet(x) << "\n";
			cout << (n - 1) - (MnGet(N - 1) - MnGet(x)) - (MxGet(x)) << "\n";
		}
	}
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51