Submission #360120

#	Time	Username	Problem	Language	Result	Execution time	Memory
360120		teehandsome	Fuel Station (NOI20_fuelstation)	C++11	24 / 100	194 ms	42768 KiB

FuelStation

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

const int mxn=3e5+10;
int n,d;
//map<int,vector<int>> ar;
vector<int> ar[mxn];
struct dt {
    int x,a,b;
    bool operator<(const dt &r) {return x<r.x;}
};
vector<dt> s;
vector<int> B;
int t[3*mxn],lazy[3*mxn];
ll sum[mxn];
ll ans=INF;

void push(int x) {
    t[2*x]+=lazy[x];
    t[2*x+1]+=lazy[x];
    lazy[2*x]+=lazy[x];
    lazy[2*x+1]+=lazy[x];
    lazy[x]=0;
}

void build(int v,int tl,int tr) {
    if(tl==tr) {
        t[v]=-s[tl].x;
        if(tl) t[v]+=sum[tl-1];
    }
    else {
        int mid=(tl+tr)/2;
        build(2*v,tl,mid);
        build(2*v+1,mid+1,tr);
        t[v]=min(t[2*v],t[2*v+1]);
    }
}
void add(int v,int tl,int tr,int l,int r,int val) {
    if(tl>tr or tl>r or tr<l) return;
    if(tl>=l and tr<=r) {
        t[v]+=val;
        lazy[v]+=val;
    }
    else {
        push(v);
        int mid=(tl+tr)/2;
        add(2*v,tl,mid,l,r,val);
        add(2*v+1,mid+1,tr,l,r,val);
        t[v]=min(t[2*v],t[2*v+1]);
    }
}
int query(int v,int tl,int tr,int l,int r) {
    if(l>r or l>tr or r<tl) return INF;
    if(tl>=l and tr<=r) {
        return t[v];
    }
    else {
        push(v);
        int mid=(tl+tr)/2;
        return min(query(2*v,tl,mid,l,r),query(2*v+1,mid+1,tr,l,r));
    }
}

int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>d; int N=n+1;
    for(int i=0;i<n;i++) {
        int x,a,b; cin>>x>>a>>b;
        s.push_back({x,a,b}); B.push_back(b);
    }
    s.push_back({d,0,d}); B.push_back(d);
    sort(all(s));
    sort(all(B)); B.erase(unique(all(B)),end(B));
    for(int i=0;i<N;i++) {
        sum[i]=s[i].a;
        if(i) sum[i]+=sum[i-1];
    }

    for(int i=0;i<N;i++) {
        //ar[s[i].b].push_back(i);
        int pos=lower_bound(all(B),s[i].b)-begin(B);
        ar[pos].push_back(i);
    }
    build(1,0,N-1);
    int past=-1;
    int cnt=0;
    for(auto e:B) {
        if(past==-1) add(1,0,N-1,0,N-1,e);
        else add(1,0,N-1,0,N-1,e-past);
        int res=query(1,0,N-1,0,N-1);
        //debug(res);
        if(res>=0) {
            cout<<e-res<<endl; return 0;
        }
        for(int u:ar[cnt]) {
            add(1,0,N-1,u+1,N-1,-s[u].a);
        }
        past=e; cnt++;
    }
}

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