Submission #758053

#	Time	Username	Problem	Language	Result	Execution time	Memory
758053		vjudge1	Simple game (IZhO17_game)	C++17	49 / 100	255 ms	22540 KiB

game

#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;
            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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 0 / 51