Submission #1125645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125645		imarn	Fuel Station (NOI20_fuelstation)	C++20	0 / 100	202 ms	15088 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;
ll t[4*mxn]{0},lz[4*mxn]{0};
void build(int i,int l,int r){
    if(l==r)return void(t[i]=1e16);
    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]);
}
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,-1e16-d);
    for(auto [b,_] : v){
        auto [x,a] = _;
        if(mp.find(x)==mp.end())update(1,1,m,ub(vx,x),ub(vx,x),-1e16-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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 12
• Subtask 5: 0 / 19
• Subtask 6: 0 / 11
• Subtask 7: 0 / 21