Submission #1106024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106024		ShadowShark	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	369 ms	42028 KiB

FuelStation

#include <bits/stdc++.h>
using namespace std;

const int maxN = 3e5 + 5;
int n, D;
int x[maxN], a[maxN], b[maxN];
pair<int, int> des[maxN];
vector<int> val, place;

struct node {
    long long val, lazy;
} st[4 * maxN];

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

    st[2 * id].val += t;
    st[2 * id + 1].val += t;

    st[2 * id].lazy += t;
    st[2 * id + 1].lazy += t;

    st[id].lazy = 0;
}

void build(int id, int l, int r) {
    if (l == r) {
        st[id].val = place[l - 1];
        return ;
    }

    int mid = (l + r) >> 1;

    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);

    st[id].val = max(st[2 * id].val, st[2 * id + 1].val);
}

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

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

    int mid = (l + r) >> 1;
    down(id);

    update(2 * id, l, mid, u, v, val);
    update(2 * id + 1, mid + 1, r, u, v, val);

    st[id].val = max(st[2 * id].val, st[2 * id + 1].val);
}

long long get(int id, int l, int r, int pos) {
    if (l == r) return st[id].val;

    int mid = (l + r) >> 1;
    down(id);

    if (pos <= mid) return get(2 * id, l, mid, pos);
    return get(2 * id + 1, mid + 1, r, pos);
}

vector<pair<int, int>> query;
long long find_ans(int res) {
    long long mn = 1e18, sum = res;
    for (int i = 1; i <= n; i++)
        if (res <= b[i]) query.push_back({x[i], a[i]});
    sort(query.begin(), query.end());
    int pre = 0;
    for (auto it: query) {
        sum = sum - (it.first - pre);
        mn = min(mn, sum);
        sum = sum + it.second;
        pre = it.first;
    }
    return res - mn;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> D;

    for (int i = 1; i <= n; i++)
        cin >> x[i] >> a[i] >> b[i];
    n++;
    x[n] = D; a[n] = 0; b[n] = D;

    for (int i = 1; i <= n; i++) {
        des[i] = {b[i], i};
        place.push_back(x[i]);
        val.push_back(b[i]);
    }

    sort(des + 1, des + n + 1);

    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    sort(place.begin(), place.end());
    place.erase(unique(place.begin(), place.end()), place.end());

    int m = place.size();
    build(1, 1, m);

    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(place.begin(), place.end(), x[i]) - place.begin() + 1;
        update(1, 1, m, pos + 1, m, -a[i]);
    }

    if (st[1].val <= val[0]) {
        cout << find_ans(val[0]);
        return 0;
    }

    int id = 1;
    for (int i = 1; i < val.size(); i++) {
        int v = val[i - 1];
        while (des[id].first == v) {
            int i = des[id].second;
            int pos = lower_bound(place.begin(), place.end(), x[i]) - place.begin() + 1;
            update(1, 1, m, pos + 1, m, a[i]);
            id++;
        }
        if (st[1].val <= val[i]) {
            cout << find_ans(val[i]);
            return 0;
        }
    }

    return 0;
}

Compilation message (stderr)

FuelStation.cpp: In function 'int main()':
FuelStation.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 1; i < val.size(); i++) {
      |                     ~~^~~~~~~~~~~~

• 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