oj.uz

Submission #515199

# Submission time Handle Problem Language Result Execution time Memory
515199 2022-01-19T04:40:02 Z Mazaalai Simple game (IZhO17_game) C++17
0 / 100
 8 ms 14668 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int M = 4*N;
int n, m;
int node[M], lazy[M], nums[N];
void propagate(int head) {
    if (lazy[head] == 0) return;
    int val = lazy[head];
    lazy[head] = 0;
    node[head*2+1] += val;
    lazy[head*2+1] += val;
    node[head*2+2] += val;
    lazy[head*2+2] += val;
}
void update(int l, int r, int L, int R, int val, int head) {
    if (l > R || L > r) return;
    if (L <= l && r <= R) {
        node[head] += val;
        lazy[head] += val;
        return;
    }
    propagate(head);
    int mid = (l+r)>>1;
    update(l, mid, L, R, val, head*2+1);
    update(mid+1, r, L, R, val, head*2+2);
    node[head] = node[head*2+1] + node[head*2+2];
}
int query(int l, int r, int id, int head) {
    if (l == r) return node[head];
    propagate(head);
    int mid = (l+r)>>1;
    if (id <= mid) return query(l, mid, id, head*2+1);
    return query(mid+1, r, id, head*2+2);
}
signed main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> nums[i];
    for (int i = 2; i <= n; i++) {
        int st = nums[i-1], end = nums[i];
        if (st > end) swap(st, end);
        update(0, N, st+1, end-1, 1, 0);
    }
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a;
        if (a == 1) {
            cin >> a >> b;
            if (a - 1 > 0) {
                int st = nums[a-1], end = nums[a];
                if (st > end) swap(st, end);
                update(0, N, st+1, end-1, -1, 0);
            }
            if (a + 1 <= n) {
                int st = nums[a], end = nums[a+1];
                if (st > end) swap(st, end);
                update(0, N, st+1, end-1, -1, 0);
            }
            nums[a] = b;
            if (a - 1 > 0) {
                int st = nums[a-1], end = nums[a];
                if (st > end) swap(st, end);
                update(0, N, st+1, end-1, -1, 0);
            }
            if (a + 1 <= n) {
                int st = nums[a], end = nums[a+1];
                if (st > end) swap(st, end);
                update(0, N, st+1, end-1, -1, 0);
            }
        } else {
            cin >> a;
            cout << query(0, N, a, 0) << '\n';
        }
    }
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Incorrect 8 ms 14668 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 316 KB Output is correct
2 Incorrect 8 ms 14668 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 316 KB Output is correct
2 Incorrect 8 ms 14668 KB Output isn't correct
3 Halted 0 ms 0 KB -