oj.uz

답안 #515239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
515239 2022-01-19T05:07:02 Z Mazaalai Simple game (IZhO17_game) C++17
100 / 100
 323 ms 19508 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);
        if (st != end) update(0, N, st+1, end-1, 1, 0);
    }
    // for (int j = 1; j <= 10; j++) cout << query(0, N, j, 0) << " \n"[j==10];
    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);
                if (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);
                if (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);
                if (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);
                if (st != end) update(0, N, st+1, end-1, 1, 0);
            }
            // for (int j = 1; j <= 10; j++) cout << query(0, N, j, 0) << " \n"[j==10];
        } else {
            cin >> a;
            cout << query(0, N, a, 0) << '\n';
        }
    }
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 9 ms 14636 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 9 ms 14668 KB Output is correct
5 Correct 8 ms 14744 KB Output is correct
6 Correct 8 ms 14624 KB Output is correct
7 Correct 6 ms 12748 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 9 ms 14636 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 9 ms 14668 KB Output is correct
5 Correct 8 ms 14744 KB Output is correct
6 Correct 8 ms 14624 KB Output is correct
7 Correct 6 ms 12748 KB Output is correct
8 Correct 48 ms 1756 KB Output is correct
9 Correct 154 ms 19296 KB Output is correct
10 Correct 126 ms 19508 KB Output is correct
11 Correct 38 ms 1596 KB Output is correct
12 Correct 77 ms 3232 KB Output is correct
13 Correct 100 ms 19228 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 9 ms 14636 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 9 ms 14668 KB Output is correct
5 Correct 8 ms 14744 KB Output is correct
6 Correct 8 ms 14624 KB Output is correct
7 Correct 6 ms 12748 KB Output is correct
8 Correct 48 ms 1756 KB Output is correct
9 Correct 154 ms 19296 KB Output is correct
10 Correct 126 ms 19508 KB Output is correct
11 Correct 38 ms 1596 KB Output is correct
12 Correct 77 ms 3232 KB Output is correct
13 Correct 100 ms 19228 KB Output is correct
14 Correct 256 ms 19304 KB Output is correct
15 Correct 323 ms 19292 KB Output is correct
16 Correct 268 ms 19240 KB Output is correct
17 Correct 258 ms 19364 KB Output is correct
18 Correct 239 ms 19364 KB Output is correct