Submission #383676

#	Time	Username	Problem	Language	Result	Execution time	Memory
383676		boykut	Simple game (IZhO17_game)	C++14	100 / 100	693 ms	19712 KiB

game

#include <bits/stdc++.h>

using namespace std;

const int N = 1000100;

int t[N * 4], tadd[4 * N];

int operate(int a, int b) {
	return a + b;
}

void push(int v, int vl, int vr) {
	if (tadd[v] != 0) {
		t[v] += tadd[v] * (vr - vl + 1);
		if (vl != vr) {
			tadd[2 * v + 1] += tadd[v];
			tadd[2 * v + 2] += tadd[v];
		}
		tadd[v] = 0;
	}
}

void update(int l, int r, int val, int v = 0, int vl = 0, int vr = N-1) {
	push(v, vl, vr);
	if (l > vr || vl > r)
		return;
	if (l <= vl && vr <= r) {
		tadd[v] = val;
		push(v, vl, vr);
		return;
	}
	int vm = (vl + vr) >> 1;
	update(l, r, val, 2 * v + 1, vl, vm);
	update(l, r, val, 2 * v + 2, vm+1, vr);
	t[v] = operate(t[2 * v + 1], t[2 * v + 2]);
}

int get(int l, int r, int v = 0, int vl = 0, int vr = N-1) {
	push(v, vl, vr);
	if (l > vr || r < vl)
		return 0;
	if (l <= vl && vr <= r)
		return t[v];
	int vm = (vl + vr) >> 1;
	return operate(get(l, r, 2 * v + 1, vl, vm),
				   get(l, r, 2 * v + 2, vm+1, vr));
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, q;
	cin >> n >> q;
	int y[n];
	for (int i = 0; i < n; i++) {
		cin >> y[i];
		if (i)
			update(min(y[i], y[i-1]), max(y[i], y[i-1]), 1);
	}
	while (q --) {
		int t;
		cin >> t;
		if (t == 1) {
			int pos, val;
			cin >> pos >> val;
			pos--;
			if (pos) update(min(y[pos], y[pos-1]), max(y[pos], y[pos-1]), -1);
			if (pos+1<n) update(min(y[pos], y[pos+1]), max(y[pos], y[pos+1]), -1);
			y[pos] = val;
			if (pos) update(min(y[pos], y[pos-1]), max(y[pos], y[pos-1]), 1);
			if (pos+1<n) update(min(y[pos], y[pos+1]), max(y[pos], y[pos+1]), 1);
		} else {
			int h;
			cin >> h;
			cout << get(h, h) << '\n';
		}
	}
	return 0;
}

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