Submission #879652

#	Time	Username	Problem	Language	Result	Execution time	Memory
879652		alex_2008	Simple game (IZhO17_game)	C++14	100 / 100	196 ms	20724 KiB

game

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <unordered_map>
#include <fstream>
#include <random>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
int fenwick1[N], fenwick2[N], a[N], mn[N], mx[N];
int MAX_V = 1000000;
void update1(int pos, int val) {
	while (pos <= MAX_V) {
		fenwick1[pos] += val;
		pos += (pos & (-pos));
	}
}
int sum1(int pos) {
	int ans = 0;
	while (pos > 0) {
		ans += fenwick1[pos];
		pos -= (pos & (-pos));
	}
	return ans;
}
void update2(int pos, int val) {
	while (pos <= MAX_V) {
		fenwick2[pos] += val;
		pos += (pos & (-pos));
	}
}
int sum2(int pos) {
	int ans = 0;
	while (pos > 0) {
		ans += fenwick2[pos];
		pos -= (pos & (-pos));
	}
	return ans;
}
int main() {
	int n, m;
	cin >> n >> m;
	map <int, int> mp;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n - 1; i++) {
		mn[i] = min(a[i], a[i + 1]);
		mx[i] = max(a[i], a[i + 1]);
		update1(mn[i], 1);
		update2(mx[i], 1);
	}
	while (m--) {
		int type;
		cin >> type;
		if (type == 2) {
			int H;
			cin >> H;
			int v1 = sum1(MAX_V) - sum1(H);
			int v2 = sum2(H - 1);
			cout << n - 1 - v1 - v2 << "\n";
		}
		else {
			int x, val;
			cin >> x >> val;
			for (int ind = x - 1; ind <= x; ind++) {
				if (ind > 0 && ind < n) {
					update1(mn[ind], -1);
					update2(mx[ind], -1);
				}
			}
			a[x] = val;
			for (int ind = x - 1; ind <= x; ind++) {
				if (ind > 0 && ind < n) {
					mn[ind] = min(a[ind], a[ind + 1]);
					mx[ind] = max(a[ind], a[ind + 1]);
				}
			}
			for (int ind = x - 1; ind <= x; ind++) {
				if (ind > 0 && ind < n) {
					update1(mn[ind], 1);
					update2(mx[ind], 1);
				}
			}
		}
	}
}

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