Submission #1248505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248505		letienbinh_812	Infinite Race (EGOI24_infiniterace2)	C++20	100 / 100	83 ms	18152 KiB

Main

#include<bits/stdc++.h>
#define N 1000000
#define inf int(1e9+7)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<long long, int> li;
typedef pair<long long, li> loli;
// loli
loli gspvhcute;
//:333


const int M = 1e9+7;
int n,m,res;


int t[N*4+4];
int lazy[N*4+4];
void down(int id){
    if(lazy[id] != 0){
        t[id*2] = lazy[id];
        t[id*2+1] = lazy[id];
        lazy[id*2] = lazy[id];
        lazy[id*2+1] = lazy[id];
        lazy[id] = 0;
    }
}
    void Update(int id, int l, int r, int u, int v, ll val){
        if(l>v || r<u) return;
        if(u<=l && r<=v){
            t[id] = val;
            lazy[id] = val;
            return;
        }
        down(id);
        int mid = (l+r)>>1;
        Update(id*2,l,mid,u,v,val);
        Update(id*2+1,mid+1,r,u,v,val);
    }

ll Get(int id, int l, int r, int pos){
        if(l>pos || r<pos) return 0;
        if(l==r) return t[id];
        down(id);
        int mid = (l+r)>>1;
        return Get(id*2,l,mid,pos) + Get(id*2+1,mid+1,r,pos);

    }
void Solve(){
    memset(t,1,sizeof(t));
    for(int x,i=1; i<=m; i++){
        cin >> x;
        if(x>0){
            if(Get(1,1,n,x) == -1){
                res++;
                Update(1,1,n,x+1,n,1);
                Update(1,1,n,1,x-1,1);
            }
            else{
                Update(1,1,n,x,x,-1);
            }
        }
        else{
            Update(1,1,n,-x,-x,1);
        }
    }
    cout << res;
}

void Inp(){
    cin >> n >> m;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int T=1;
//    cin >> T;
    while(T--){
    Inp();
    Solve();
    }
}
//-----YEU CODE HON CRUSH-----//

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