oj.uz

Submission #340906

# Submission time Handle Problem Language Result Execution time Memory
340906 2020-12-28T13:37:12 Z Tosic Simple game (IZhO17_game) C++14
0 / 100
 12 ms 18540 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){
	if(idx*2+2 >= maxn){
		return;
	}
	tree[idx] += lazy[idx]*(r-l+1);
	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){
	
	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);
}


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]);
	}
	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;
			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
0 / 22.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 51.0

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