Submission #1148224

#TimeUsernameProblemLanguageResultExecution timeMemory
1148224Ghulam_JunaidInfinite Race (EGOI24_infiniterace2)C++20
100 / 100
79 ms3568 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 100;
int n, val[4 * N];

void upd(int l, int r, int x, int v = 1, int s = 1, int e = n){
    if (r <= s || e <= l) return ;
    if (l <= s && e <= r){
        val[v] = x;
        return ;
    }

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
    if (val[v] != -1)
        val[lc] = val[rc] = val[v], val[v] = -1;

    upd(l, r, x, lc, s, mid);
    upd(l, r, x, rc, mid, e);
}

int get(int p, int v = 1, int s = 1, int e = n){
    if (val[v] != -1) return val[v];
    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
    if (p < mid) return get(p, lc, s, mid);
    return get(p, rc, mid, e);
}

int main(){
    memset(val, -1, sizeof val);

    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;

    for (int i = 1; i < n; i ++)
        upd(i, i + 1, 1);

    int q;
    cin >> q;
    int ans = 0;
    while (q--){
        int i;
        cin >> i;

        if (i < 0){
            i = -i;
            upd(i, i + 1, 1);
        }
        else{
            if (get(i)){
                upd(i, i + 1, 0);
            }
            else{
                upd(1, n, 1);
                upd(i, i + 1, 0);
                ans++;
            }
        }
    }

    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...