Submission #957429

#	Time	Username	Problem	Language	Result	Execution time	Memory
957429		starchan	Simple game (IZhO17_game)	C++17	100 / 100	72 ms	11160 KiB

game

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
const int LMX  = 1e6+6;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int fen[LMX];
void upd(int x, int val)
{
	for(int pos = x; pos < LMX; pos+=(pos&-pos))
		fen[pos]+=val;
	return;
}
int query(int x)
{
	int ret = 0;
	for(int pos = x; pos; pos-=(pos&-pos))
		ret+=fen[pos];
	return ret;
}
void add(int l, int r, int d)
{
	if(l > r)
		swap(l, r);
	upd(l, d); upd(r+1, -d);
	return;
}
signed main()
{
	fast();
	int n, m;
	cin >> n >> m;
	vector<int> h(n+1);
	for(int i = 1; i <= n; i++)
	{
		cin >> h[i];
		if(i > 1)
			add(h[i-1], h[i], 1);
	}
	while(m--)
	{
		int t, x; cin >> t >> x; t--;
		if(t)
			cout << query(x) << "\n";
		else
		{
			if(x > 1)
				add(h[x-1], h[x], -1);
			if(x < n)
				add(h[x], h[x+1], -1);
			cin >> h[x];
			if(x > 1)
				add(h[x-1], h[x], 1);
			if(x < n)
				add(h[x], h[x+1], 1);
		}
	}
	return 0;
}	

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