Submission #901695

#	Time	Username	Problem	Language	Result	Execution time	Memory
901695		OAleksa	Simple game (IZhO17_game)	C++14	100 / 100	55 ms	12992 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 1e6 + 69;
int n, q, a[N], f[N];
void add(int v, int val) {
	for (int i = v;i < N;i += (i & -i))
		f[i] += val;
}
int get(int v) {
	int r = 0;
	for (int i = v;i > 0;i -= (i & -i))
		r += f[i];
	return r;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
	  cin >> n >> q;
	  for (int i = 1;i <= n;i++)
	  	cin >> a[i];
	  for (int i = 2;i <= n;i++) {
	  	int x = a[i - 1], y = a[i];
	  	if (x > y)
	  		swap(x, y);
	  	add(x, 1);
	  	add(y + 1, -1);
	  }
	  while (q--) {
	  	int t;
	  	cin >> t;
	  	if (t == 1) {
	  		int x, val;
	  		cin >> x >> val;
	  		if (x != 1) {
	  			int mn = a[x - 1];
	  			int mx = a[x];
	  			if (mn > mx)
	  				swap(mn, mx);
	  			add(mn, -1);
	  			add(mx + 1, 1);
	  		}
	  		if (x != n) {
	  			int mn = a[x];
	  			int mx = a[x + 1];
	  			if (mn > mx)
	  				swap(mn, mx);
	  			add(mn, -1);
	  			add(mx + 1, 1);
	  		}
	  		a[x] = val;
	  		if (x != 1) {
	  			int mn = a[x - 1];
	  			int mx = a[x];
	  			if (mn > mx)
	  				swap(mn, mx);
	  			add(mn, 1);
	  			add(mx + 1, -1);
	  		}
	  		if (x != n) {
	  			int mn = a[x];
	  			int mx = a[x + 1];
	  			if (mn > mx)
	  				swap(mn, mx);
	  			add(mn, 1);
	  			add(mx + 1, -1);
	  		}
	  	}
	  	else {
	  		int x;
				cin >> x;
	  		cout << get(x) << '\n';
	  	}
	  }
	}
  return 0;
}

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