Submission #648491

#	Time	Username	Problem	Language	Result	Execution time	Memory
648491		ymm	Simple game (IZhO17_game)	C++17	100 / 100	73 ms	6948 KiB

game

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1'000'010;

int fen[N];
void add(int r, int x)
{
	while (r > 0) {
		fen[r] += x;
		r -= r & -r;
	}
}
int get(int i)
{
	int ans = 0;
	++i;
	while (i < N) {
		ans += fen[i];
		i += i & -i;
	}
	return ans;
}
void add(int l, int r, int x)
{
	add(r, x);
	add(l, -x);
}

int p[N];
int n;

void add_diff(int i, int mul)
{
	int l = min(p[i], p[i+1]);
	int r = max(p[i], p[i+1]);
	add(l+1, r, mul);
}

void update_pnt(int i, int x)
{
	if (i > 0)
		add_diff(i-1, -1);
	if (i < n-1)
		add_diff(i, -1);
	p[i] = x;
	if (i > 0)
		add_diff(i-1, 1);
	if (i < n-1)
		add_diff(i, 1);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int q;
	cin >> n >> q;
	Loop (i,0,n)
		cin >> p[i];
	Loop (i,0,n-1)
		add_diff(i, 1);
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int i, y;
			cin >> i >> y;
			update_pnt(i-1, y);
		} else {
			int h;
			cin >> h;
			cout << get(h) << '\n';
		}
	}
}

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