oj.uz

Submission #169053

# Submission time Handle Problem Language Result Execution time Memory
169053 2019-12-18T05:54:20 Z tselmegkh Simple game (IZhO17_game) C++14
100 / 100
 751 ms 36420 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
long long tree[8000050], h[N], lazy[8000050];

void update(int v, int l, int r, int ql, int qr, int del){
	if(ql > qr || l > r)return;
	if(lazy[v] != 0){
		tree[v] += lazy[v];
		if(l != r){
			lazy[2 * v] += lazy[v];
			lazy[2 * v + 1] += lazy[v];
		}
		lazy[v] = 0;
	}
	if(ql > r || qr < l)return;
	if(ql <= l && qr >= r){
		tree[v] += del;
		if(l != r){
			lazy[2 * v] += del;
			lazy[2 * v + 1] += del;
		}
		return;
	}
	int mid = (l + r) / 2;
	update(v * 2, l, mid, ql, qr, del);
	update(v * 2 + 1, mid + 1, r, ql, qr, del);
	tree[v] = tree[v * 2] + tree[v * 2 + 1];
}
long long query(int v, int l, int r, int ql, int qr){
	if(l > r)return 0;
	if(lazy[v] != 0){
		tree[v] += lazy[v];
		if(l != r){
			lazy[v * 2] += lazy[v];
			lazy[v * 2 + 1] += lazy[v];
		}
		lazy[v] = 0;
	}
	if(ql > r || qr < l)return 0;
	if(ql == l && qr == r){
		return tree[v];
	}
	int mid = (l + r) / 2;
	return query(v * 2, l, mid, ql, qr) + query(v * 2 + 1, mid + 1, r, ql, qr);
}
int main(){
	int n, q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> h[i];
		if(i > 1){
			update(1, 1, 1000000, min(h[i], h[i - 1]) + 1, max(h[i], h[i - 1]) - 1, 1);
		}
	}
	while(q--){
		int type;
		cin >> type;
		if(type == 1){
			int pos, val;
			cin >> pos >> val;
			if(pos > 1)update(1, 1, 1000000, min(h[pos - 1], h[pos]) + 1, max(h[pos - 1], h[pos]) - 1, -1), update(1, 1, 1000000, min((long long)val, h[pos - 1]) + 1, max((long long)val, h[pos - 1]) - 1, 1);
			if(pos < n)update(1, 1, 1000000, min(h[pos + 1], h[pos]) + 1, max(h[pos + 1], h[pos]) - 1, -1), update(1, 1, 1000000, min((long long)val, h[pos + 1]) + 1, max((long long)val, h[pos + 1]) - 1, 1);
			h[pos] = val;
		}else{
			int val;
			cin >> val;
			cout << query(1, 1, 1000000, val, val) << '\n';
		}
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 28 ms 24568 KB Output is correct
3 Correct 27 ms 23900 KB Output is correct
4 Correct 27 ms 24564 KB Output is correct
5 Correct 27 ms 24312 KB Output is correct
6 Correct 27 ms 24440 KB Output is correct
7 Correct 22 ms 19192 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 28 ms 24568 KB Output is correct
3 Correct 27 ms 23900 KB Output is correct
4 Correct 27 ms 24564 KB Output is correct
5 Correct 27 ms 24312 KB Output is correct
6 Correct 27 ms 24440 KB Output is correct
7 Correct 22 ms 19192 KB Output is correct
8 Correct 402 ms 2168 KB Output is correct
9 Correct 614 ms 36216 KB Output is correct
10 Correct 619 ms 36344 KB Output is correct
11 Correct 365 ms 2056 KB Output is correct
12 Correct 492 ms 4244 KB Output is correct
13 Correct 559 ms 36216 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 28 ms 24568 KB Output is correct
3 Correct 27 ms 23900 KB Output is correct
4 Correct 27 ms 24564 KB Output is correct
5 Correct 27 ms 24312 KB Output is correct
6 Correct 27 ms 24440 KB Output is correct
7 Correct 22 ms 19192 KB Output is correct
8 Correct 402 ms 2168 KB Output is correct
9 Correct 614 ms 36216 KB Output is correct
10 Correct 619 ms 36344 KB Output is correct
11 Correct 365 ms 2056 KB Output is correct
12 Correct 492 ms 4244 KB Output is correct
13 Correct 559 ms 36216 KB Output is correct
14 Correct 725 ms 36172 KB Output is correct
15 Correct 751 ms 36300 KB Output is correct
16 Correct 717 ms 36420 KB Output is correct
17 Correct 713 ms 36188 KB Output is correct
18 Correct 744 ms 36348 KB Output is correct