oj.uz

Submission #570716

# Submission time Handle Problem Language Result Execution time Memory
570716 2022-05-31T06:41:32 Z saarang123 Simple game (IZhO17_game) C++17
100 / 100
 71 ms 6844 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MXN = 100 * 1000 + 3;
const int MXM = 1000 * 1000 + 3;
int bit[MXM], a[MXN], n, q;

void upd(int x, int v = 1) {
	for(; x < MXM; x += (x & -x))
		bit[x] += v;
}

void upd(int l, int r, int v) {
	upd(l, v);
	upd(r + 1, -v);
}

int qry(int x) {
	int res = 0;
	for(; x > 0; x -= (x & -x))
		res += bit[x];
	return res;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
    	cin >> a[i];
    	if(i > 1) {
    		int x = min(a[i - 1], a[i]);
    		int y = max(a[i - 1], a[i]);
    		upd(x, y, 1);
    	}
    }
    while(q--) {
    	int tp; cin >> tp;
    	if(tp == 1) {
    		int i, val;
    		cin >> i >> val;
    		if(i > 1) {
	    		int x = min(a[i - 1], a[i]);
	    		int y = max(a[i - 1], a[i]);
	    		upd(x, y, -1);
    		}
    		if(i < n) {
    			int x = min(a[i + 1], a[i]);
	    		int y = max(a[i + 1], a[i]);
	    		upd(x, y, -1);
    		}
    		a[i] = val;
    		if(i > 1) {
	    		int x = min(a[i - 1], a[i]);
	    		int y = max(a[i - 1], a[i]);
	    		upd(x, y, 1);
    		}
    		if(i < n) {
    			int x = min(a[i + 1], a[i]);
	    		int y = max(a[i + 1], a[i]);
	    		upd(x, y, 1);
    		}
    	} else {
    		int h; cin >> h;
    		cout << qry(h) << '\n';
    	}
    }
    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 2 ms 4052 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 1 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 2 ms 4052 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 34 ms 1236 KB Output is correct
9 Correct 51 ms 6840 KB Output is correct
10 Correct 45 ms 6812 KB Output is correct
11 Correct 32 ms 1612 KB Output is correct
12 Correct 41 ms 2788 KB Output is correct
13 Correct 38 ms 2800 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 2 ms 4052 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 34 ms 1236 KB Output is correct
9 Correct 51 ms 6840 KB Output is correct
10 Correct 45 ms 6812 KB Output is correct
11 Correct 32 ms 1612 KB Output is correct
12 Correct 41 ms 2788 KB Output is correct
13 Correct 38 ms 2800 KB Output is correct
14 Correct 63 ms 6784 KB Output is correct
15 Correct 61 ms 6824 KB Output is correct
16 Correct 58 ms 6844 KB Output is correct
17 Correct 59 ms 6792 KB Output is correct
18 Correct 71 ms 6732 KB Output is correct