Submission #1244457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244457		nwtk	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	242 ms	28588 KiB

FuelStation

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 3e5;

struct station {
    int x, f, r;
};

vector <station> stations,order;

long long int initial[MAXN+1],diff[MAXN+1];

struct node {
    long long int min1;
    long long int sum;
    node operator+ (node& other) {
        return {min(min1+other.sum,other.min1), sum+other.sum};
    }
};

node tree[4*(MAXN+1)];

void build_tree(int ind, int l, int r) {
    if (l == r) {
        tree[ind] = {diff[l], diff[l]};
        return ;
    }

    int mid = (l + r) >> 1;
    build_tree(2*ind + 1, l, mid);
    build_tree(2*ind + 2, mid + 1, r);
    tree[ind] = tree[2*ind + 1] + tree[2*ind + 2];
}

void update(int ind, int l, int r, int pos, int val) {
    if (l == r) {
        tree[ind].min1 += val;
        tree[ind].sum += val;
        
        return ;
    }

    int mid = (l + r) >> 1;
    if (pos<=mid) update(2*ind + 1, l, mid, pos, val);
    else update(2*ind + 2, mid + 1, r, pos, val);
    tree[ind] = tree[2*ind + 1] + tree[2*ind + 2];
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n,l;
    cin >> n >> l ;
    stations.resize(n);
    for (auto& [x, f, r] : stations) {
        cin >> x >> f >> r ;
    }
    stations.push_back({l, 0, (int)1e9});
    n++;

    sort(stations.begin(), stations.end(), [](station& s1, station& s2) {
         return (s1.x < s2.x) || ((s1.x == s2.x) && (s1.r < s2.r));
    });

    long long int sumf=0;
    for (int i=0; i<n; i++) {
        auto [x, f, r]=stations[i];
        initial[i]=sumf-x;
        sumf+=f;
    }

    diff[n-1]=initial[n-1];
    for (int i=n-2; i>=0; i--) {
        diff[i]=initial[i]-initial[i+1];
    }
    build_tree(0,0,n-1);

    order.reserve(n);
    for (int i=0; i<n; i++) {
        auto [x, f, r]=stations[i];
        order.push_back({i, f, r});
    }
    sort(order.begin(),order.end(),[] (station& s1, station& s2){
         return (s1.r < s2.r);
    });

    int prv = 0;
    for (int i = 0; i < n; i++) {
        update(0, 0, n-1, n-1, order[i].r - prv);
        prv = order[i].r;
        if (tree[0].min1 >= 0) {
            cout << order[i].r - tree[0].min1;
            break;
        }

        for (int j = i; j < n; j++) {
            auto [x, f, r] = order[j];
            if (r != order[i].r) {
                i = j - 1;
                break;
            }
            if (x != n-1) {
                update(0, 0, n-1, n-1, -f);
                update(0, 0, n-1, x, f);
            }
            if (j == n-1) i = n-1;
        }
    }

    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