Submission #1189066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189066		yellowtoad	Simple game (IZhO17_game)	C++20	100 / 100	187 ms	9544 KiB

game

#include <iostream>
using namespace std;

int n, test, a[100010], node[4000010];

void update(int id, int x, int y, int l, int r, int val) {
	if (l > r) return;
	if ((l <= x) && (y <= r)) {
		node[id] += val;
		return;
	}
	if ((y < l) || (r < x)) return;
	int mid = (x+y)/2;
	node[id*2] += node[id];
	node[id*2+1] += node[id];
	node[id] = 0;
	update(id*2,x,mid,l,r,val);
	update(id*2+1,mid+1,y,l,r,val);
}

int query(int id, int x, int y, int pos) {
	if (x == y) return node[id];
	int mid = (x+y)/2;
	node[id*2] += node[id];
	node[id*2+1] += node[id];
	node[id] = 0;
	if (pos <= mid) return query(id*2,x,mid,pos);
	else return query(id*2+1,mid+1,y,pos);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> test;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i < n; i++) update(1,1,1e6,min(a[i],a[i+1])+1,max(a[i],a[i+1])-1,1);
	while (test--) {
		int type, pos, val;
		cin >> type;
		if (type == 1) {
			cin >> pos >> val;
			if (pos != 1) update(1,1,1e6,min(a[pos-1],a[pos])+1,max(a[pos-1],a[pos])-1,-1);
			if (pos != n) update(1,1,1e6,min(a[pos+1],a[pos])+1,max(a[pos+1],a[pos])-1,-1);
			a[pos] = val;
			if (pos != 1) update(1,1,1e6,min(a[pos-1],a[pos])+1,max(a[pos-1],a[pos])-1,1);
			if (pos != n) update(1,1,1e6,min(a[pos+1],a[pos])+1,max(a[pos+1],a[pos])-1,1);
		} else {
			cin >> val;
			cout << query(1,1,1e6,val) << "\n";
		}
	}
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51