Submission #1194705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194705		anna_yarosh	Infinite Race (EGOI24_infiniterace2)	C++17	100 / 100	16 ms	3580 KiB

Main

#include <bits/stdc++.h>
#include <random>

using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")

typedef unsigned long long ull;

#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double

#define pll pair <ll, ll>
#define pb push_back

const ll DIM = 2e5+7;
const ll bsize = 450;
const ll INF = 1e9;
const ll mln = 1e6+7;
const ll maxn = 30;
const ll mod = 1e9+7;
const ld gold = ((1+sqrt(5))/2);
const ll max_val = 1LL<<40LL;

//ll n, m, w, nq, mx, val, x, y, k, v1, v2, cost, day, g, l, r, start, finish;
ll cnt[DIM], a[DIM], nextt[DIM], prevv[DIM];

string s, type;

void solve(){

    ll n, q, x;

    cin>>n>>q;


    for(int i=1; i<=n; i++){
        nextt[i] = 1;
        prevv[i] = 0;
    }

    ll res = 0;
    ll curr = 0;

    for(int i=1; i<=q; i++){

        cin>>x;

        if(x < 0){
            nextt[abs(x)] = 1;
            prevv[abs(x)] = 0;
        }

        if(x > 0){

            if(nextt[x] == 1){
                nextt[x] = 0;
                prevv[x] = curr;
                continue;
            }

            if(prevv[x] == curr){
                res++;
                curr++;
                nextt[x] = 0;
                prevv[x] = curr;
                continue;
            }

            nextt[x] = 0;
            prevv[x] = curr;
        }
    }

    cout<<res<<endl;
     


}

signed main(){

    speed;

    int test = 1;
    //cin>>test;

    while(test--){
        solve();
    }

    return 0;

}

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