oj.uz

Submission #36385

# Submission time Handle Problem Language Result Execution time Memory
36385 2017-12-08T14:35:48 Z cheater2k Simple game (IZhO17_game) C++14
100 / 100
 603 ms 41628 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41628 KB Output is correct
2 Correct 3 ms 41628 KB Output is correct
3 Correct 6 ms 41628 KB Output is correct
4 Correct 9 ms 41628 KB Output is correct
5 Correct 3 ms 41628 KB Output is correct
6 Correct 9 ms 41628 KB Output is correct
7 Correct 3 ms 41628 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41628 KB Output is correct
2 Correct 3 ms 41628 KB Output is correct
3 Correct 6 ms 41628 KB Output is correct
4 Correct 9 ms 41628 KB Output is correct
5 Correct 3 ms 41628 KB Output is correct
6 Correct 9 ms 41628 KB Output is correct
7 Correct 3 ms 41628 KB Output is correct
8 Correct 106 ms 41628 KB Output is correct
9 Correct 299 ms 41628 KB Output is correct
10 Correct 273 ms 41628 KB Output is correct
11 Correct 96 ms 41628 KB Output is correct
12 Correct 166 ms 41628 KB Output is correct
13 Correct 156 ms 41628 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41628 KB Output is correct
2 Correct 3 ms 41628 KB Output is correct
3 Correct 6 ms 41628 KB Output is correct
4 Correct 9 ms 41628 KB Output is correct
5 Correct 3 ms 41628 KB Output is correct
6 Correct 9 ms 41628 KB Output is correct
7 Correct 3 ms 41628 KB Output is correct
8 Correct 106 ms 41628 KB Output is correct
9 Correct 299 ms 41628 KB Output is correct
10 Correct 273 ms 41628 KB Output is correct
11 Correct 96 ms 41628 KB Output is correct
12 Correct 166 ms 41628 KB Output is correct
13 Correct 156 ms 41628 KB Output is correct
14 Correct 569 ms 41628 KB Output is correct
15 Correct 603 ms 41628 KB Output is correct
16 Correct 496 ms 41628 KB Output is correct
17 Correct 539 ms 41628 KB Output is correct
18 Correct 556 ms 41628 KB Output is correct