Submission #1122467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122467		AnhPham	Fuel Station (NOI20_fuelstation)	C++20	67 / 100	3089 ms	14408 KiB

FuelStation

#include <bits/stdc++.h>

using namespace std;

#define int     long long
#define sz(r)   (int)(r).size()
#define all(r)  (r).begin(), (r).end()

const   int     MOD = (int)1e9 + 7;
const   int     INF = (int)4e18 + 18;

void solve();

int32_t main() {
#define CODE "task"
    if (fopen(CODE".inp", "r"))
        freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);

    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
    int testcases = 1;

#define multitest 0
    if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/** [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] **/
/**                            The Last Dance                            **/

struct FUELSTATION {
    int X, A, B;

    bool operator < (const FUELSTATION &other) const {
        return (X == other.X ? A < other.A : X < other.X);
    }
};

int N, D;
vector <FUELSTATION> stations;

namespace sub1 {
    bool check_condition() {
        return N == 1;
    }

    void solve() {
        cout << (max(stations[0].X, D - stations[0].A) <= stations[0].B ? max(stations[0].X, D - stations[0].A) : D) << '\n';
    }
}

namespace sub2 {
    bool check_condition() {
        for (auto item : stations)
            if (item.B != 1e9)
                return 0;

        return 1;
    }

    void solve() {
        sort(all(stations));

        int ans = 0;
        int sum = 0;
        for (int i = 0; i < sz(stations); ++i) {
            ans = max(ans, stations[i].X - sum);
            sum += stations[i].A;
        }

        ans = max(ans, D - sum);

        cout << ans << '\n';
    }
}

namespace sub356 {
    bool check_condition() {
        return N <= 1e4;
    }

    bool possible(int f) {
        int F = f;
        for (int i = 1; i < sz(stations); ++i) {
            f -= stations[i].X - stations[i - 1].X;

            if (f < 0)
                return 0;

            if (F > stations[i].B)
                continue;

            f += stations[i].A;
        }

        return 1;
    }

    void solve() {
        stations.push_back({ 0, 0, (int)1e9 });
        stations.push_back({ D, 0, (int)1e9 });
        sort(all(stations));

        vector <int> max_fuel = { D };
        for (auto item : stations)
            max_fuel.push_back(item.B);

        sort(all(max_fuel));
        int hi = D;
        for (auto d : max_fuel)
            if (possible(d)) {
                 hi = d;
                 break;
            }

        int ans = -1;
            int lo = 0;
            while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (possible(mid))
                ans = mid, hi = mid - 1;
            else
                lo = mid + 1;
        }

        cout << ans << '\n';
    }
}

namespace sub47 {
    const int mxN = 3e5 + 5;

    struct dta {
        int B, id;

        bool operator < (const dta &other) const {
            return B < other.B;
        }
    };

    struct node {
        int val, lazy;
    } st[4 * mxN];

    vector <dta> dta;
    vector <int> compressed_X, compressed_B;

    void down(int id) {
        int t = st[id].lazy;

        st[id << 1].val += t;
        st[id << 1 | 1].val += t;

        st[id << 1].lazy += t;
        st[id << 1 | 1].lazy += t;

        st[id].lazy = 0;
    }

    void build(int id, int left, int right) {
        if (left == right)
            return void(st[id].val = compressed_X[left - 1]);

        int mid = (left + right) >> 1;
        build(id << 1, left, mid);
        build(id << 1 | 1, mid + 1, right);

        st[id].val = max(st[id << 1].val, st[id << 1 | 1].val);
    }

    void update(int id, int left, int right, int l, int r, int val) {
        if (r < left || right < l)
            return;

        if (l <= left && right <= r) {
            st[id].lazy += val;
            st[id].val += val;
            return;
        }

        down(id);

        int mid = (left + right) >> 1;
        update(id << 1, left, mid, l, r, val);
        update(id << 1 | 1, mid + 1, right, l, r, val);

        st[id].val = max(st[id << 1].val, st[id << 1 | 1].val);
    }

    int get(int id, int left, int right, int pos) {
        if (left == right)
            return st[id].val;

        down(id);

        int mid = (left + right) >> 1;
        if (pos <= mid)
            return get(id << 1, left, mid, pos);

        return get(id << 1 | 1, mid + 1, right, pos);
    }

    vector <pair <int, int>> query;
    int find_ans(int f) {
        int mn = 1e18, sum = f;
        for (int i = 0; i < sz(stations); i++)
            if (f <= stations[i].B)
                query.push_back({ stations[i].X, stations[i].A });

        sort(all(query));
        int pre = 0;
        for (auto it: query) {
            sum = sum - (it.first - pre);
            mn = min(mn, sum);
            sum = sum + it.second;
            pre = it.first;
        }

        return f - mn;
    }


    void solve() {
        stations.push_back({ D, 0, (int)1e9 });
        for (int i = 0; i < sz(stations); ++i) {
            dta.push_back({ stations[i].B, i });
            compressed_X.push_back(stations[i].X);
            compressed_B.push_back(stations[i].B);
        }

        sort(all(dta));
        sort(all(compressed_X));
        sort(all(compressed_B));
        compressed_X.erase(unique(all(compressed_X)), compressed_X.end());
        compressed_B.erase(unique(all(compressed_B)), compressed_B.end());

        int m = sz(compressed_X) - 1;
        build(1, 1, m);

        for (int i = 0; i < sz(stations); ++i) {
            int pos = lower_bound(all(compressed_X), stations[i].X) - compressed_X.begin() + 1;
            update(1, 1, m, pos + 1, m, -stations[i].A);
        }

        if (st[1].val <= compressed_B[0])
            return void(cout << find_ans(compressed_B[0]) << '\n');

        int id = 1;
        for (int i = 1; i < sz(compressed_B); i++) {
            int r = compressed_B[i - 1];
            while (dta[id].B == r) {
                int i = dta[id].id;
                int pos = lower_bound(all(compressed_X), stations[i].X) - compressed_X.begin() + 1;
                update(1, 1, m, pos + 1, m, stations[i].A);
                id++;
            }

            if (st[1].val <= compressed_B[i])
                return void(cout << find_ans(compressed_B[i]) << '\n');
        }
    }
}

void solve() {
    cin >> N >> D;

    stations = vector <FUELSTATION> (N);
    for (auto &item : stations)
        cin >> item.X >> item.A >> item.B;

//    if (sub1 :: check_condition())
//        sub1 :: solve();
//    else if (sub2 :: check_condition)
//        sub2 :: solve();
//    else if (sub356 :: check_condition())
        sub356 :: solve();
//    else
//        sub47 :: solve();
}

Compilation message (stderr)

FuelStation.cpp: In function 'int32_t main()':
FuelStation.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
FuelStation.cpp:17:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 0 / 21