Submission #340947

#	Time	Username	Problem	Language	Result	Execution time	Memory
340947		Tosic	Simple game (IZhO17_game)	C++14	100 / 100	513 ms	26988 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51