Submission #1244455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244455		nguyenkhangninh99	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	702 ms	61660 KiB

FuelStation

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

const int maxn = 3e5 + 5;

struct ttt{
    int x, a, b;
} tram[maxn];

bool cmp(ttt c1, ttt c2){
    return c1.x < c2.x;
}

vector<pair<int, int>> tram2[10005];

int st[4 * maxn], lazy[4 * maxn];

void fix(int id, int l, int r){
    if (!lazy[id]) return;
    st[id] += lazy[id];
 
    if (l != r){
        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, int val){
    fix(id, l, r);
    if (v < l || r < u) return;
    if (u <= l && r <= v){
        lazy[id] += val;
        fix(id, l, r);
        return;
    }
 
    int mid = l+r>>1;
    update(id*2, l, mid, u, v, val);
    update(id*2+1, mid+1, r, u, v, val);
    st[id] = min(st[id*2], st[id*2+1]);
}
 
 
void solve(){
   int n, d; cin >> n >> d;

    int mn = 1e9;
    for(int i = 1; i <= n; i++){
        cin >> tram[i].x >> tram[i].a >> tram[i].b;
        mn = min(mn, tram[i].b);
    }
    
    tram[++n]={d,0,d};
    sort(tram + 1, tram + n + 1, cmp);;

    vector<int> v, ans(n + 1);
    map<int, vector<int>> mp;

    for(int i = 1; i <= n; i++){
        v.push_back(tram[i].b);
        mp[tram[i].b].push_back(i);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 1; i <= n; i++){
        update(1, 1, n, i, i, v[0] - tram[i].x);
        int l = i + 1, r = n;
        while(l <= r){
            int mid = (l + r) / 2;
            if(tram[mid].x > tram[i].x){
                ans[i] = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }

        if(ans[i] > 0) update(1, 1, n, ans[i], n, tram[i].a);
    }

    int kq = 1e15;
    int z = st[1];
    if(z >= 0) kq = min(kq, v[0] - z);
    for(int i = 1; i < v.size(); i++){
        update(1, 1, n, 1, n, v[i] - v[i - 1]);
        for(int y: mp[v[i - 1]]){
            if(ans[y] > 0) update(1, 1, n, ans[y], n, -tram[y].a);
        }
        z = st[1];
        if(z >= 0) kq = min(kq, v[i] - z);
    }
    
    cout << kq;
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
}

• 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