oj.uz

Submission #546736

# Submission time Handle Problem Language Result Execution time Memory
546736 2022-04-08T10:24:29 Z syrtin Simple game (IZhO17_game) C++17
100 / 100
 204 ms 11196 KB 
#include <bits/stdc++.h>
#define ss second
#define ff first
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e6 + 123;
const int mod = 998244353;
const int inf = 1e9;
int wt;
int cnt[N * 4], h, x, y;
void upd(int v, int l, int r) {
	if(x <= l && r <= y){
		cnt[v] += wt;
		return;
	}
	if(r < x || y < l)return;
	int mid = l + (r - l) / 2;
	upd(v * 2 + 1, l, mid), upd(v * 2 + 2, mid + 1, r);
}
int get(int v, int l, int r) {
	if(l == r) {
		return cnt[v];
	}
	int mid = l + (r - l) / 2;
	if(h <= mid)return cnt[v] + get(v * 2 + 1, l, mid);
	else return cnt[v] + get(v * 2 + 2, mid + 1, r);
}
void solve() {
	int n, m;
	cin >> n >> m;
	int a[n];
	wt = 1;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		if(i){
			x = a[i], y = a[i - 1];
			if(x > y)swap(x, y);
			upd(0, 0, N);
		}
	}
	while(m--) {
		int type;
		cin >> type;
		if(type == 1) {
			int pos, val;
			cin >> pos >> val;
			wt = -1;
			if(pos != n) {
				x = a[pos - 1], y = a[pos];
				if(x > y)swap(x, y);
				upd(0, 0, N);
			}
			if(pos != 1) {
				x = a[pos - 1], y = a[pos - 2];
				if(x > y) swap(x, y);
				upd(0, 0, N);
			}
			a[pos - 1] = val, wt = 1;
			if(pos != n) {
				x = a[pos - 1], y = a[pos];
				if(x > y)swap(x, y);
				upd(0, 0, N);
			}
			if(pos != 1) {
				x = a[pos - 1], y = a[pos - 2];
				if(x > y) swap(x, y);
				upd(0, 0, N);
			}
		}
		else {
			cin >> h;
			cout << get(0, 0, N) << '\n';
		}
	}
}
int main() {
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 6696 KB Output is correct
3 Correct 5 ms 6356 KB Output is correct
4 Correct 5 ms 6484 KB Output is correct
5 Correct 6 ms 6444 KB Output is correct
6 Correct 5 ms 6484 KB Output is correct
7 Correct 2 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 6696 KB Output is correct
3 Correct 5 ms 6356 KB Output is correct
4 Correct 5 ms 6484 KB Output is correct
5 Correct 6 ms 6444 KB Output is correct
6 Correct 5 ms 6484 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 40 ms 1612 KB Output is correct
9 Correct 89 ms 11068 KB Output is correct
10 Correct 118 ms 11068 KB Output is correct
11 Correct 39 ms 1600 KB Output is correct
12 Correct 64 ms 2908 KB Output is correct
13 Correct 78 ms 2804 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 6696 KB Output is correct
3 Correct 5 ms 6356 KB Output is correct
4 Correct 5 ms 6484 KB Output is correct
5 Correct 6 ms 6444 KB Output is correct
6 Correct 5 ms 6484 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 40 ms 1612 KB Output is correct
9 Correct 89 ms 11068 KB Output is correct
10 Correct 118 ms 11068 KB Output is correct
11 Correct 39 ms 1600 KB Output is correct
12 Correct 64 ms 2908 KB Output is correct
13 Correct 78 ms 2804 KB Output is correct
14 Correct 204 ms 11072 KB Output is correct
15 Correct 164 ms 11064 KB Output is correct
16 Correct 177 ms 11072 KB Output is correct
17 Correct 204 ms 11064 KB Output is correct
18 Correct 163 ms 11196 KB Output is correct