Submission #1134538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134538		Agageldi	Simple game (IZhO17_game)	C++17	100 / 100	67 ms	17224 KiB

game

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 2000005
#define pb push_back
#define ff first
#define ss second
#define sz(s) (int)s.size()

ll n, t, a[N], p[N], m, fb[N], fg[N], vis[N];
void solve(int x,int y,int bal) {
	while(x > 0) {
		fb[x] += bal;
		x -= (x&(-x));
	}
	while(y <= 1e6) {
		fg[y] += bal;
		y += (y&(-y));
	}
}
int find(int x,int y) {
	int sum = 0;
	while(x > 0) {
		sum += fg[x];
		x-= (x&(-x));
	}
	while(y <= 1e6) {
		sum += fb[y];
		y += (y & (-y));
	}
	return sum;
}

int main (){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		if(i > 1) solve(min(a[i],a[i-1]), max(a[i],a[i - 1]), 1);
	}
	for(int i = 1; i <= m; i++) {
		int x, y;
		cin >> t;
		
		if(t == 1) {
			cin >> x >> y;
			if(x != 1)solve(min(a[x],a[x-1]),max(a[x],a[x-1]),-1);
			if(x != n)solve(min(a[x],a[x+1]),max(a[x],a[x+1]),-1);
			a[x] = y;
			if(x != 1)solve(min(a[x], a[x-1]),max(a[x],a[x-1]),1);
			if(x != n)solve(min(a[x], a[x+1]),max(a[x],a[x+1]),1);
			continue;
		}
		cin >> x;
		int ans = find(x - 1, x + 1);
		cout << n - 1 - ans << '\n';
	}
}

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