Submission #36385

#	Time	Username	Problem	Language	Result	Execution time	Memory
36385		cheater2k	Simple game (IZhO17_game)	C++14	100 / 100	603 ms	41628 KiB

game

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int MAX = 1000010;

int n, m, h[N];
int T[5 * MAX], lz[5 * MAX];

#define mid ((l + r) >> 1)
void push(int v, int l, int r) {
	if (lz[v] == 0) return;
	if (l < r) lz[v << 1] += lz[v], lz[v << 1 | 1] += lz[v];
	T[v] += lz[v]; lz[v] = 0;
} 

void upd(int v, int l, int r, int L, int R, int val) {
	push(v, l, r);
	if (l > r || R < l || L > r) return;
	if (L <= l && r <= R) { lz[v] = val; push(v, l, r); return; }
	upd(v << 1, l, mid, L, R, val); upd(v << 1 | 1, mid + 1, r, L, R, val);
	T[v] = max(T[v << 1], T[v << 1 | 1]);
}

int get(int v, int l, int r, int pos) {
	push(v, l, r);
	if (l > r || l > pos || r < pos) return 0;
	if (l == r) return T[v];
	return max(get(v << 1, l, mid, pos), get(v << 1 | 1, mid + 1, r, pos));
}
#undef mid

void process(int pos, int val) {
	if (pos > 1) upd(1, 1, MAX, min(h[pos-1], h[pos]), max(h[pos-1], h[pos]), val);
	if (pos < n) upd(1, 1, MAX, min(h[pos], h[pos+1]), max(h[pos], h[pos+1]), val);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> h[i];
	for (int i = 1; i < n; ++i) {
		int l = min(h[i], h[i + 1]), r = max(h[i], h[i + 1]);
		upd(1, 1, MAX, l, r, +1);
	}	

	while(m--) {
		int type; cin >> type;
		if (type == 1) {
			int pos, val; cin >> pos >> val;
			process(pos, -1); // delete the old point
			h[pos] = val;
			process(pos, +1); // update new changes
		} else {
			int H; cin >> H;
			printf("%d\n", get(1, 1, MAX, H));
		}
	}
}

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