oj.uz

Submission #377313

# Submission time Handle Problem Language Result Execution time Memory
377313 2021-03-13T21:16:15 Z ijxjdjd Simple game (IZhO17_game) C++14
100 / 100
 238 ms 11372 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXH = (int)(1e6) + 5;

int lzy[4*MAXH];
void upd(int l, int r, int val, int n=1, int tl=0, int tr=MAXH-1) {
    if (l > r) {
        swap(l, r);
    }
    if (l > tr || r < tl) {
        return;
    }
    else if (l <= tl && tr <= r) {
        lzy[n] += val;
    }
    else {
        int tm = (tl + tr)/2;
        upd(l, r, val, 2*n, tl, tm);
        upd(l, r, val, 2*n+1, tm+1, tr);
    }
}
int get(int i, int n=1, int tl=0,int tr=MAXH-1) {
    if (tl == tr) {
        return lzy[n];
    }
    int tm = (tl + tr)/2;
    if (i <= tm) {
        return lzy[n] + get(i, 2*n, tl, tm);
    }
    else {
        return lzy[n] + get(i, 2*n+1, tm+1, tr);
    }
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	vector<int> v(N);
	FR(i, N) {
        cin >> v[i];
	}
    for (int i = 1; i < N; i++) {
        upd(v[i-1], v[i], 1);
    }
    FR(iter, M) {
        int id;
        cin >> id;
        if (id == 1) {
            int p, val;
            cin >> p >> val;
            p--;
            if (p > 0) {
                upd(v[p-1], v[p], -1);
                upd(v[p-1], val, 1);
            }
            if (p < N-1) {
                upd(v[p], v[p+1], -1);
                upd(val, v[p+1], 1);
            }
            v[p] = val;
        }
        else {
            int H;
            cin >> H;
            cout << get(H) << '\n';
        }
    }
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 6 ms 6636 KB Output is correct
3 Correct 7 ms 6508 KB Output is correct
4 Correct 6 ms 6636 KB Output is correct
5 Correct 7 ms 6528 KB Output is correct
6 Correct 6 ms 6508 KB Output is correct
7 Correct 2 ms 492 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 6 ms 6636 KB Output is correct
3 Correct 7 ms 6508 KB Output is correct
4 Correct 6 ms 6636 KB Output is correct
5 Correct 7 ms 6528 KB Output is correct
6 Correct 6 ms 6508 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 49 ms 1900 KB Output is correct
9 Correct 120 ms 11140 KB Output is correct
10 Correct 119 ms 11244 KB Output is correct
11 Correct 52 ms 1772 KB Output is correct
12 Correct 77 ms 3052 KB Output is correct
13 Correct 83 ms 2924 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 6 ms 6636 KB Output is correct
3 Correct 7 ms 6508 KB Output is correct
4 Correct 6 ms 6636 KB Output is correct
5 Correct 7 ms 6528 KB Output is correct
6 Correct 6 ms 6508 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 49 ms 1900 KB Output is correct
9 Correct 120 ms 11140 KB Output is correct
10 Correct 119 ms 11244 KB Output is correct
11 Correct 52 ms 1772 KB Output is correct
12 Correct 77 ms 3052 KB Output is correct
13 Correct 83 ms 2924 KB Output is correct
14 Correct 213 ms 11116 KB Output is correct
15 Correct 238 ms 11116 KB Output is correct
16 Correct 217 ms 11244 KB Output is correct
17 Correct 238 ms 11244 KB Output is correct
18 Correct 219 ms 11372 KB Output is correct