oj.uz

Submission #901695

# Submission time Handle Problem Language Result Execution time Memory
901695 2024-01-10T00:44:16 Z OAleksa Simple game (IZhO17_game) C++14
100 / 100
 55 ms 12992 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 8668 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 8668 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 31 ms 9452 KB Output is correct
9 Correct 38 ms 12888 KB Output is correct
10 Correct 37 ms 12880 KB Output is correct
11 Correct 32 ms 9556 KB Output is correct
12 Correct 32 ms 10684 KB Output is correct
13 Correct 35 ms 10584 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 8668 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 31 ms 9452 KB Output is correct
9 Correct 38 ms 12888 KB Output is correct
10 Correct 37 ms 12880 KB Output is correct
11 Correct 32 ms 9556 KB Output is correct
12 Correct 32 ms 10684 KB Output is correct
13 Correct 35 ms 10584 KB Output is correct
14 Correct 52 ms 12972 KB Output is correct
15 Correct 55 ms 12884 KB Output is correct
16 Correct 53 ms 12908 KB Output is correct
17 Correct 52 ms 12992 KB Output is correct
18 Correct 48 ms 12988 KB Output is correct