Submission #216512

#	Time	Username	Problem	Language	Result	Execution time	Memory
216512		someone_aa	Simple game (IZhO17_game)	C++17	100 / 100	366 ms	19492 KiB

game

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;

const int maxc = 1000100;
const int maxn = 100100;

int tree[4*maxc];
int lazy[4*maxc];

int n, q, arr[maxn];

void push_update(int li, int ri, int index) {
	if(lazy[index] != 0) {
		tree[index] += lazy[index] * (ri - li + 1);

		if(li != ri) {
			lazy[2*index] += lazy[index];
			lazy[2*index+1] += lazy[index];
		}
		lazy[index] = 0;
	}
}

void update(int ul, int ur, int uval, int li=0, int ri=maxc-1, int index=1) {
	push_update(li, ri, index);
	if(ul > ur) return;

	if(li > ur || ri < ul) return;
	else if(li >= ul && ri <= ur) {
		lazy[index] += uval;
		push_update(li, ri, index);
	}
	else {
		int mid = (li + ri) / 2;
		update(ul, ur, uval, li, mid, 2*index);
		update(ul, ur, uval, mid+1, ri, 2*index+1);

		tree[index] = tree[2*index] + tree[2*index+1];
	}
}

int query(int qind, int li=0, int ri=maxc-1, int index=1) {
	push_update(li, ri, index);

	if(li == ri) return tree[index];
	else {
		int mid = (li + ri) / 2;

		if(qind <= mid) return query(qind, li, mid, 2*index);
		else return query(qind, mid+1, ri, 2*index+1);
	}
}

void removeindex(int i) {
	if(i == 1 || i > n) return;

	if(abs(arr[i] - arr[i-1]) <= 1) return;

	if(arr[i-1] > arr[i]) {
		update(arr[i]+1, arr[i-1]-1, -1);
	}
	else {
		update(arr[i-1]+1, arr[i]-1, -1);
	}
}

void addindex(int i) {
	if(i == 1 || i > n) return;

	if(abs(arr[i] - arr[i-1]) <= 1) return;

	if(arr[i-1] > arr[i]) {
		update(arr[i]+1, arr[i-1]-1, 1);
	}
	else {
		update(arr[i-1]+1, arr[i]-1, 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>arr[i];
		if(i > 1) {
			if(abs(arr[i] - arr[i-1]) <= 1) continue;

			if(arr[i-1] > arr[i]) {
				update(arr[i]+1, arr[i-1]-1, 1);
			}
			else {
				update(arr[i-1]+1, arr[i]-1, 1);
			}
		}
	}

	int qtype;
	while(q--) {
		cin>>qtype;

		int ind, val;
		if(qtype == 2) {
			cin>>ind;
			cout<<query(ind)<<"\n";
		}
		else {
			cin>>ind>>val;
			removeindex(ind);
			removeindex(ind+1);

			arr[ind] = val;
			addindex(ind);
			addindex(ind+1);
		}
	}
}

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