oj.uz

Submission #1085601

# Submission time Handle Problem Language Result Execution time Memory
1085601 2024-09-08T13:15:16 Z coolboy19521 Simple game (IZhO17_game) C++17
100 / 100
 310 ms 22960 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 (mi >= 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 (n + 1 == v) return;
    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 = 1e6 + 5;
    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
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 7 ms 18696 KB Output is correct
3 Correct 6 ms 18776 KB Output is correct
4 Correct 6 ms 18780 KB Output is correct
5 Correct 7 ms 18760 KB Output is correct
6 Correct 7 ms 18780 KB Output is correct
7 Correct 5 ms 17244 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 7 ms 18696 KB Output is correct
3 Correct 6 ms 18776 KB Output is correct
4 Correct 6 ms 18780 KB Output is correct
5 Correct 7 ms 18760 KB Output is correct
6 Correct 7 ms 18780 KB Output is correct
7 Correct 5 ms 17244 KB Output is correct
8 Correct 161 ms 13908 KB Output is correct
9 Correct 223 ms 22884 KB Output is correct
10 Correct 240 ms 22868 KB Output is correct
11 Correct 143 ms 13620 KB Output is correct
12 Correct 195 ms 15188 KB Output is correct
13 Correct 220 ms 22612 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 7 ms 18696 KB Output is correct
3 Correct 6 ms 18776 KB Output is correct
4 Correct 6 ms 18780 KB Output is correct
5 Correct 7 ms 18760 KB Output is correct
6 Correct 7 ms 18780 KB Output is correct
7 Correct 5 ms 17244 KB Output is correct
8 Correct 161 ms 13908 KB Output is correct
9 Correct 223 ms 22884 KB Output is correct
10 Correct 240 ms 22868 KB Output is correct
11 Correct 143 ms 13620 KB Output is correct
12 Correct 195 ms 15188 KB Output is correct
13 Correct 220 ms 22612 KB Output is correct
14 Correct 272 ms 22868 KB Output is correct
15 Correct 275 ms 22868 KB Output is correct
16 Correct 310 ms 22960 KB Output is correct
17 Correct 280 ms 22800 KB Output is correct
18 Correct 273 ms 22836 KB Output is correct