oj.uz

Submission #1085588

# Submission time Handle Problem Language Result Execution time Memory
1085588 2024-09-08T13:02:40 Z coolboy19521 Simple game (IZhO17_game) C++17
0 / 100
 13 ms 13876 KB 
#include "bits/stdc++.h"
#define ll long long

using namespace std;

const int sz = 2e6 + 2;

int st[sz * 4], lz[sz * 4];
int ln, n;

void relax(int v, int lo, int hi) {
    st[v] += lz[v];
    if (lo != hi) {
        lz[v * 2] += lz[v];
        lz[v * 2 + 1] += lz[v];
    }
    lz[v] = 0;
}

void upd(int lo, int hi, int ql, int qr, int v, int k) {
    relax(v, lo, hi);
    if (lo > qr or ql > hi)
        return;
    if (ql <= lo and hi <= qr) {
        lz[v] += k;
        relax(v, lo, hi);
    } else {
        int mi = (lo + hi) / 2;
        upd(lo, mi, ql, qr, v * 2, k);
        upd(mi + 1, hi, ql, qr, v * 2 + 1, k);
    }
}

int qry(int ix) {
    int lo = 1, hi = ln, v = 1;
    while (lo != hi) {
        relax(v, lo, hi);
        int mi = (lo + hi) / 2;
        if (hi > ix)
            hi = mi, v *= 2;
        else lo = mi + 1, v = v * 2 + 1;
    }
    relax(v, lo, hi);
    return st[v];
}

int a[sz];

void cng(int v, int k) {
    if (1 != v and 1 < abs(a[v - 1] - a[v])) {
        int c = min(a[v - 1], a[v]) + 1;
        int d = max(a[v - 1], a[v]) - 1;
        upd(1, ln, c, d, 1, k);
    }
}

int main() {
    int m; cin >> n >> m;
    ln = sz - 1;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i]; cng(i, 1);
    }
    while (m --) {
        int t; cin >> t;
        if (1 == t) {
            int p, v; cin >> p >> v;
            cng(p, -1); cng(p + 1, -1);
            a[p] = v;
            cng(p, 1); cng(p + 1, 1);
        } else {
            int x; cin >> x;
            cout << qry(x) << '\n';
        }
    }
}

Subtask #1
0 / 22.0

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