Submission #799168

#	Time	Username	Problem	Language	Result	Execution time	Memory
799168		AndiR	Fuel Station (NOI20_fuelstation)	C++14	36 / 100	276 ms	13944 KiB

FuelStation

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

using namespace std;
const int Nmax=300000;

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

bool cmp(station a, station b){
    return a.x<b.x;
}
int main()
{
    cin>>n>>d;
    for (int 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;
    int fs=0, fadd=0;
    for (int 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: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 0 / 19
• Subtask 6: 0 / 11
• Subtask 7: 0 / 21