Submission #1148224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148224		Ghulam_Junaid	Infinite Race (EGOI24_infiniterace2)	C++20	100 / 100	79 ms	3568 KiB

Main

#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;
}

• Subtask 1: 29 / 29
• Subtask 2: 34 / 34
• Subtask 3: 22 / 22
• Subtask 4: 15 / 15