oj.uz

답안 #1085602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1085602 2024-09-08T13:15:39 Z vjudge1 Simple game (IZhO17_game) C++17
100 / 100
 278 ms 21848 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 7 ms 18764 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Correct 6 ms 18780 KB Output is correct
5 Correct 6 ms 18844 KB Output is correct
6 Correct 9 ms 18780 KB Output is correct
7 Correct 5 ms 17244 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 7 ms 18764 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Correct 6 ms 18780 KB Output is correct
5 Correct 6 ms 18844 KB Output is correct
6 Correct 9 ms 18780 KB Output is correct
7 Correct 5 ms 17244 KB Output is correct
8 Correct 162 ms 13144 KB Output is correct
9 Correct 222 ms 21328 KB Output is correct
10 Correct 229 ms 21332 KB Output is correct
11 Correct 177 ms 12888 KB Output is correct
12 Correct 199 ms 13668 KB Output is correct
13 Correct 229 ms 21848 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 7 ms 18764 KB Output is correct
3 Correct 6 ms 19036 KB Output is correct
4 Correct 6 ms 18780 KB Output is correct
5 Correct 6 ms 18844 KB Output is correct
6 Correct 9 ms 18780 KB Output is correct
7 Correct 5 ms 17244 KB Output is correct
8 Correct 162 ms 13144 KB Output is correct
9 Correct 222 ms 21328 KB Output is correct
10 Correct 229 ms 21332 KB Output is correct
11 Correct 177 ms 12888 KB Output is correct
12 Correct 199 ms 13668 KB Output is correct
13 Correct 229 ms 21848 KB Output is correct
14 Correct 278 ms 20812 KB Output is correct
15 Correct 273 ms 20820 KB Output is correct
16 Correct 268 ms 20816 KB Output is correct
17 Correct 264 ms 20820 KB Output is correct
18 Correct 267 ms 21024 KB Output is correct