Submission #169053

#	Time	Username	Problem	Language	Result	Execution time	Memory
169053		tselmegkh	Simple game (IZhO17_game)	C++14	100 / 100	751 ms	36420 KiB

game

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