Submission #1125651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125651		imarn	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	722 ms	45036 KiB

FuelStation

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=3e5+5;
vector<pair<ll,pll>>v;
vector<ll>vx;
map<ll,int>mp;
const ll inf = 1e16;
ll t[4*mxn]{0},lz[4*mxn]{0};
void build(int i,int l,int r){
    if(l==r)return void(t[i]=inf);
    int m=(l+r)>>1;
    build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]=min(t[2*i],t[2*i+1]);
}
void push(int i,int l,int r){
    t[i]+=lz[i];
    if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
    lz[i]=0;
}
void update(int i,int l,int r,int tl,int tr,ll v){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i]+=v;push(i,l,r);return;
    }int m=(l+r)>>1;
    update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
    t[i]=min(t[2*i],t[2*i+1]);
}
ll qr(int i,int l,int r,int idx){
    push(i,l,r);
    if(r<idx||l>idx)return 2e16;
    if(l==r)return t[i];
    int m=(l+r)>>1;
    return min(qr(2*i,l,m,idx),qr(2*i+1,m+1,r,idx));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;ll d;cin>>n>>d;vx.pb(d);
    for(int i=1;i<=n;i++){
        ll x,a,b;cin>>x>>a>>b;v.pb({b,{x,a}});vx.pb(x);
    }sort(all(v),greater<pair<ll,pll>>());sort(all(vx));vx.erase(unique(all(vx)),vx.end());
    m=vx.size();build(1,1,m);ll rs=d;
    update(1,1,m,m,m,-inf-d);
    for(auto [b,_] : v){
        auto [x,a] = _;
        if(mp.find(x)==mp.end())update(1,1,m,ub(vx,x),ub(vx,x),-inf-x),mp[x]=1;
        update(1,1,m,ub(vx,x)+1,m,a);
        ll tt = t[1];
        if(-tt<=b)rs=min(rs,-tt);
    }
    cout<<rs;
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 21 / 21