Submission #799171

#	Time	Username	Problem	Language	Result	Execution time	Memory
799171		AndiR	Fuel Station (NOI20_fuelstation)	C++14	100 / 100	287 ms	24704 KiB

FuelStation

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll Nmax=300000;

ll n, d;
struct station{
    ll x, a, b;
}v[Nmax+1];
priority_queue <pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;

bool cmp(station a, station b){
    return a.x<b.x;
}
int main()
{
    cin>>n>>d;
    for (ll i=0; i<n; i++)
        cin>>v[i].x>>v[i].a>>v[i].b;
    sort(v, v+n, cmp);
    v[n].x=d; v[n].b=d+1;
    ll fs=0, fadd=0;
    for (ll i=0; i<=n; i++){
        while (v[i].x>fs+fadd && fs<=v[i].b){
            fs=v[i].x-fadd;
            while (!q.empty() && q.top().first<fs){
                fadd-=q.top().second;
                q.pop();
            }
        }
        if (fs<=v[i].b){
            fadd+=v[i].a;
            q.push({v[i].b, v[i].a});
        }
    }
    cout<<fs;
    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