oj.uz

Submission #36384

# Submission time Handle Problem Language Result Execution time Memory
36384 2017-12-08T14:32:55 Z cheater2k Simple game (IZhO17_game) C++14
0 / 100
 3 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, n, min(h[pos-1], h[pos]), max(h[pos-1], h[pos]), val);
	if (pos < n) upd(1, 1, n, 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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41628 KB Output is correct
2 Incorrect 3 ms 41628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41628 KB Output is correct
2 Incorrect 3 ms 41628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41628 KB Output is correct
2 Incorrect 3 ms 41628 KB Output isn't correct
3 Halted 0 ms 0 KB -