제출 #1321181

#제출 시각아이디문제언어결과실행 시간메모리
132118112345678Fuel Station (NOI20_fuelstation)C++20
13 / 100
209 ms15956 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=3e5+5;

ll n, d, x[nx], a[nx], b[nx], t, cx[nx], rv[nx], res;
map<ll, vector<ll>> mp;
map<ll, ll> cmp;

struct segtree
{
    ll mn[4*nx], lz[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return mn[i]=-rv[l], void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        mn[i]=min(mn[2*i], mn[2*i+1]);
    }
    void pushlz(int l, int r, int i)
    {
        mn[i]+=lz[i];
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql||qr<ql) return;
        if (ql<=l&&r<=qr) return lz[i]=vl, pushlz(l, r, i);
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        mn[i]=min(mn[2*i], mn[2*i+1]);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>d;
    for (int i=1; i<=n; i++) cin>>x[i]>>a[i]>>b[i], mp[b[i]].push_back(i), cmp[x[i]]=0;
    cmp[d]=0;
    for (auto &[x, y]:cmp) y=++t, rv[t]=x;
    for (int i=1; i<=n; i++) cx[i]=cmp[x[i]];
    s.build(1, t, 1);
    res=d;
    for (auto itr=mp.rbegin(); itr!=mp.rend(); itr++)
    {
        vector<ll> event=itr->second;
        ll bound=itr->first;
        for (auto idx:event) s.update(1, t, 1, cx[idx]+1,  t, a[idx]);
        if (s.mn[1]<=bound) res=min(res, -s.mn[1]);
    }
    cout<<res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...