oj.uz

Submission #340947

# Submission time Handle Problem Language Result Execution time Memory
340947 2020-12-28T15:58:12 Z Tosic Simple game (IZhO17_game) C++14
100 / 100
 513 ms 26988 KB 
#include <bits/stdc++.h>
#define maxn 4000010
using namespace std;

int n, m, h[maxn];
int tree[maxn], lazy[maxn], maxH;

void prop(int idx, int l, int r){
	tree[idx] += lazy[idx]*(r-l+1);
	if(idx*2+2  < maxn){
		lazy[idx*2+1] += lazy[idx];
		lazy[idx*2+2] += lazy[idx];
	}
	lazy[idx] = 0;
}

int query(int idx, int l, int r, int ql, int qr){
	prop(idx, l, r);
	if(l > qr or r < ql){
		return 0;
	}
	if(l >= ql and r<=qr){
		return tree[idx];
	}
	int mid = (l+r)/2;
	return query(idx*2+1, l, mid, ql, qr) + query(idx*2+2, mid+1, r, ql, qr);
}

int query1(int idx, int l, int r, int x){
	prop(idx, l, r);
	if(l == r){
		return tree[idx];
	}
	int mid = (l+r)/2;
	if(x > mid){
		return query1(idx*2+2, mid+1,r,x);
	} else {
		return query1(idx*2+1, l, mid, x);
	}
}

void upd(int idx, int l, int r, int ql, int qr, int newV){
	prop(idx, l, r);
	if(l > qr or r < ql){
		return;
	}
	if(l >= ql and r <= qr){
		lazy[idx] += newV;
		prop(idx, l, r);
		return;
	}
	int mid = (l+r)/2;
	upd(idx*2+1, l, mid, ql, qr, newV);
	upd(idx*2+2, mid+1, r, ql, qr, newV);
	tree[idx] = tree[idx*2+1] + tree[idx*2+2];
}


int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		cin >> h[i];
		//maxH = max(maxH, h[i]);
	}
	maxH = 1000010;
	for(int i = 0; i < n; ++i){
		if(i){
			upd(0, 0, maxH, min(h[i-1], h[i]), max(h[i], h[i-1]), 1);
		}
	}
	for(int i = 0; i < m; ++i){
		int t,x,y;
		cin >> t;
		if(t == 2){
			cin >> x;
			if(x > maxH){
				cout << 0 << '\n';
				continue;
			}
			cout << query1(0, 0, maxH,x) << '\n';
		} else {
			cin >> x >> y;
			x--;
			if(x){
				upd(0, 0, maxH, min(h[x-1], h[x]), max(h[x], h[x-1]), -1);
			}
			if(x < n-1){
				upd(0, 0, maxH, min(h[x+1], h[x]), max(h[x], h[x+1]), -1);
			}
			h[x] = y;
			if(x){
				upd(0, 0, maxH, min(h[x-1], h[x]), max(h[x], h[x-1]), 1);
			}
			if(x < n-1){
				upd(0, 0, maxH, min(h[x+1], h[x]), max(h[x], h[x+1]), 1);
			}
		}
	}
}

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 19180 KB Output is correct
3 Correct 15 ms 18540 KB Output is correct
4 Correct 15 ms 18924 KB Output is correct
5 Correct 15 ms 19052 KB Output is correct
6 Correct 16 ms 18924 KB Output is correct
7 Correct 10 ms 15596 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 19180 KB Output is correct
3 Correct 15 ms 18540 KB Output is correct
4 Correct 15 ms 18924 KB Output is correct
5 Correct 15 ms 19052 KB Output is correct
6 Correct 16 ms 18924 KB Output is correct
7 Correct 10 ms 15596 KB Output is correct
8 Correct 88 ms 1900 KB Output is correct
9 Correct 230 ms 26860 KB Output is correct
10 Correct 228 ms 26860 KB Output is correct
11 Correct 82 ms 1900 KB Output is correct
12 Correct 134 ms 3564 KB Output is correct
13 Correct 184 ms 26648 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 19180 KB Output is correct
3 Correct 15 ms 18540 KB Output is correct
4 Correct 15 ms 18924 KB Output is correct
5 Correct 15 ms 19052 KB Output is correct
6 Correct 16 ms 18924 KB Output is correct
7 Correct 10 ms 15596 KB Output is correct
8 Correct 88 ms 1900 KB Output is correct
9 Correct 230 ms 26860 KB Output is correct
10 Correct 228 ms 26860 KB Output is correct
11 Correct 82 ms 1900 KB Output is correct
12 Correct 134 ms 3564 KB Output is correct
13 Correct 184 ms 26648 KB Output is correct
14 Correct 503 ms 26860 KB Output is correct
15 Correct 503 ms 26988 KB Output is correct
16 Correct 498 ms 26860 KB Output is correct
17 Correct 513 ms 26860 KB Output is correct
18 Correct 491 ms 26860 KB Output is correct