Submission #1277728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277728		aryan	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	224 ms	28624 KiB

FuelStation

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

const int N = 3e5 + 1;
vector<i64> tree(4 * N,0);
vector<i64> lazy(4 * N,0);

void build(int ind,int nl,int nr,vector<i64> &pref){
    if(nl == nr){
        tree[ind] = pref[nl];
    }else{
        int mid = (nl + nr) / 2;
        build(2 * ind,nl,mid,pref);
        build(2 * ind + 1,mid + 1,nr,pref);
        tree[ind] = min(tree[2 * ind],tree[2 * ind + 1]);
    }
}

void dolazy(int ind){
    tree[2 * ind] += lazy[ind];
    tree[2 * ind + 1] += lazy[ind];
    lazy[2 * ind] += lazy[ind];
    lazy[2 * ind + 1] += lazy[ind];
    lazy[ind] = 0;
}

void update(int ind,int nl,int nr,int l,int r,int v){
    if(nl > r || l > nr) return;
    if(l <= nl && nr <= r){
        tree[ind] -= v;
        lazy[ind] -= v;
        return;
    }
    int mid = (nl + nr) / 2;
    dolazy(ind);
    update(2 * ind,nl,mid,l,r,v);
    update(2 * ind + 1,mid + 1,nr,l,r,v);
    tree[ind] = min(tree[2 * ind],tree[2 * ind + 1]);
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n,d;
    cin >> n >> d;
    vector<int> x(n),a(n),b(n);
    for(int i = 0;i < n;i++){
        cin >> x[i] >> a[i] >> b[i];
    }   
    vector<int> ind(n);
    iota(ind.begin(),ind.end(),0);
    sort(ind.begin(),ind.end(),[&](int i,int j){
        return x[i] < x[j];
    });

    vector<int> ind2(n);
    iota(ind2.begin(),ind2.end(),0);
    sort(ind2.begin(),ind2.end(),[&](int i,int j){
        return b[i] < b[j];
    });


    vector<i64> pref(n + 1);
    i64 tot = 0;
    vector<int> hs(n);
    for(int i = 0;i < n;i++){
        int e = ind[i];
        hs[e] = i;
        if(i) pref[i] = pref[i - 1] - (x[e] - x[ind[i - 1]]) + a[ind[i - 1]]; 
        else pref[i] = -x[e];
        tot = max(tot,-1LL * pref[i]);
    }
    pref[n] = pref[n - 1] - (d - x[ind[n - 1]]) + a[ind[n - 1]]; 
    tot = max(tot,-1LL * pref[n]);
    i64 f = d;
    if(tot <= b[ind2[0]]){
        f = tot;
    }
    build(1,0,n,pref);
    for(int i = 0;i < n;i++){
        // f is between (b[i] to b[i + 1]];
        int e = ind2[i];    
        int e2 = hs[e];
        i64 my = 0;
        update(1,0,n,e2 + 1,n,a[e]);
        my = -1LL * tree[1];
        if(b[e] < my && my <= (i + 1 < n ? b[ind2[i + 1]] : d)){
            f = min(f,my);
        }
    }
    cout << f << '\n';

    return 0;
}

• 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