oj.uz

Submission #758062

# Submission time Handle Problem Language Result Execution time Memory
758062 2023-06-14T06:07:04 Z vjudge1 Simple game (IZhO17_game) C++17
100 / 100
 307 ms 22604 KB 
#include"bits/stdc++.h"
using namespace std;
#define ll long long
const ll mod = 1000000007;

int N, Left, Right, pos, val;
int ans[1000001], seg[5000000], lazy[5000000];

void spread(int ind) {
    seg[ind * 2] += lazy[ind];
    seg[ind * 2 + 1] += lazy[ind];
    lazy[ind * 2] += lazy[ind];
    lazy[ind * 2 + 1] += lazy[ind];
    lazy[ind] = 0;
}

void update(int l = 1, int r = N, int ind = 1) {
    if(l > Right || r < Left)
        return;
    if(l != r)
        spread(ind);
    if(l >= Left && r <= Right) {
        lazy[ind] += val;
        seg[ind] += val;
        return;
    }
    int mid = (l + r) / 2;
    update(l, mid, ind * 2);
    update(mid + 1, r, ind * 2 + 1);
    seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
}

int get_ans(int l = 1, int r = N, int ind = 1) {
    if(l > pos || r < pos)
        return 0;
    if(l == r)
        return seg[ind];
    spread(ind);
    int mid = (l + r) / 2;
    return get_ans(l, mid, ind * 2) + get_ans(mid + 1, r, ind * 2 + 1);
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;
    int h[n + 1];
    N = exp2(ceil(log2(1000000)));
    for(int i = 1; i <= n; i++) {
        cin >> h[i];
        ans[h[i]]++;
    }
    for(int i = 1; i < n; i++) {
        Left = min(h[i], h[i + 1]);
        Right = h[i] + h[i + 1] - Left;
        Left++, Right--;
        if(Left > Right)
            continue;
        val = 1;
        update();
    }
    while(m--) {
        int type;
        cin >> type;
        if(type == 1) {
            int ind, new_h;
            cin >> ind >> new_h;
            ans[h[ind]]--;
            for(int i = max(ind - 1, 1); i <= min(ind, n - 1); i++) {
                Left = min(h[i], h[i + 1]);
                Right = h[i] + h[i + 1] - Left;
                Left++, Right--;
                if(Left > Right)
                    continue;
                val = -1;
                update();
            }
            h[ind] = new_h;
            ans[h[ind]]++;
            for(int i = max(ind - 1, 1); i <= min(ind, n - 1); i++) {
                Left = min(h[i], h[i + 1]);
                Right = h[i] + h[i + 1] - Left;
                Left++, Right--;
                if(Left > Right)
                    continue;
                val = 1;
                update();
            }
        }
        else if(type == 2) {
            cin >> pos;
            cout << ans[pos] + get_ans() << "\n";
        }
    }

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 17808 KB Output is correct
3 Correct 11 ms 17364 KB Output is correct
4 Correct 11 ms 17700 KB Output is correct
5 Correct 11 ms 17748 KB Output is correct
6 Correct 11 ms 17712 KB Output is correct
7 Correct 8 ms 12488 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 17808 KB Output is correct
3 Correct 11 ms 17364 KB Output is correct
4 Correct 11 ms 17700 KB Output is correct
5 Correct 11 ms 17748 KB Output is correct
6 Correct 11 ms 17712 KB Output is correct
7 Correct 8 ms 12488 KB Output is correct
8 Correct 55 ms 1472 KB Output is correct
9 Correct 152 ms 22476 KB Output is correct
10 Correct 175 ms 22472 KB Output is correct
11 Correct 38 ms 1680 KB Output is correct
12 Correct 91 ms 3276 KB Output is correct
13 Correct 113 ms 18432 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 17808 KB Output is correct
3 Correct 11 ms 17364 KB Output is correct
4 Correct 11 ms 17700 KB Output is correct
5 Correct 11 ms 17748 KB Output is correct
6 Correct 11 ms 17712 KB Output is correct
7 Correct 8 ms 12488 KB Output is correct
8 Correct 55 ms 1472 KB Output is correct
9 Correct 152 ms 22476 KB Output is correct
10 Correct 175 ms 22472 KB Output is correct
11 Correct 38 ms 1680 KB Output is correct
12 Correct 91 ms 3276 KB Output is correct
13 Correct 113 ms 18432 KB Output is correct
14 Correct 302 ms 22432 KB Output is correct
15 Correct 292 ms 22604 KB Output is correct
16 Correct 291 ms 22528 KB Output is correct
17 Correct 279 ms 22468 KB Output is correct
18 Correct 307 ms 22480 KB Output is correct