oj.uz

Submission #377312

# Submission time Handle Problem Language Result Execution time Memory
377312 2021-03-13T21:15:45 Z ijxjdjd Simple game (IZhO17_game) C++14
0 / 100
 6 ms 6636 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);
            }
        }
        else {
            int H;
            cin >> H;
            cout << get(H) << '\n';
        }
    }
	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 6 ms 6636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 6 ms 6636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 6 ms 6636 KB Output isn't correct
3 Halted 0 ms 0 KB -