oj.uz

Submission #383676

# Submission time Handle Problem Language Result Execution time Memory
383676 2021-03-30T14:03:06 Z boykut Simple game (IZhO17_game) C++14
100 / 100
 693 ms 19712 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 16 ms 15084 KB Output is correct
3 Correct 16 ms 14828 KB Output is correct
4 Correct 16 ms 15084 KB Output is correct
5 Correct 16 ms 15084 KB Output is correct
6 Correct 16 ms 15084 KB Output is correct
7 Correct 13 ms 12780 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 16 ms 15084 KB Output is correct
3 Correct 16 ms 14828 KB Output is correct
4 Correct 16 ms 15084 KB Output is correct
5 Correct 16 ms 15084 KB Output is correct
6 Correct 16 ms 15084 KB Output is correct
7 Correct 13 ms 12780 KB Output is correct
8 Correct 347 ms 1900 KB Output is correct
9 Correct 553 ms 19564 KB Output is correct
10 Correct 526 ms 19436 KB Output is correct
11 Correct 334 ms 1900 KB Output is correct
12 Correct 420 ms 3308 KB Output is correct
13 Correct 475 ms 19436 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 16 ms 15084 KB Output is correct
3 Correct 16 ms 14828 KB Output is correct
4 Correct 16 ms 15084 KB Output is correct
5 Correct 16 ms 15084 KB Output is correct
6 Correct 16 ms 15084 KB Output is correct
7 Correct 13 ms 12780 KB Output is correct
8 Correct 347 ms 1900 KB Output is correct
9 Correct 553 ms 19564 KB Output is correct
10 Correct 526 ms 19436 KB Output is correct
11 Correct 334 ms 1900 KB Output is correct
12 Correct 420 ms 3308 KB Output is correct
13 Correct 475 ms 19436 KB Output is correct
14 Correct 693 ms 19692 KB Output is correct
15 Correct 668 ms 19308 KB Output is correct
16 Correct 682 ms 19436 KB Output is correct
17 Correct 667 ms 19712 KB Output is correct
18 Correct 679 ms 19436 KB Output is correct