Submission #1127387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127387		Tsagana	Simple game (IZhO17_game)	C++17	100 / 100	155 ms	9416 KiB

game

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int a[1000001];
int d[1000001];

void ad(int l, int r) {
	for (; l <= 1000000; l += (l & -l)) d[l] += r;
}


void add(int l, int r, int k) {
	if (l > r) swap(l, r);
	ad(l, k);
	ad(r + 1, -k);
}

int get(int x) {
	int ans = 0;
	for (; x > 0; x -= (x & -x)) ans += d[x];
	return ans;
}

void solve () {
	int n, q; cin >> n >> q;
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (i != 1) add(a[i], a[i - 1], 1);
	}
	
	while(q--){
		int l, r, t; cin >> t >> l;
		if (t == 1) {
			cin >> r;
			if (l > 1) {
				add(a[l - 1], r, 1);
				add(a[l - 1], a[l], -1);
			}
			if (l < n) {
				add(a[l + 1], r, 1);
				add(a[l + 1], a[l], -1);
			}
			a[l] = r;
		}
		else cout << get(l) << '\n';
	}
}
signed main() {IOS solve(); return 0;}

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