Submission #1170827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170827		nguyenkhangninh99	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	534 ms	45016 KiB

FuelStation

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 3e5 + 5;
array<int, 3> b[maxn];

struct SegmentTree{
    int st[4 * maxn], lazy[4 * maxn];
    void add(int id, int val){
        st[id] += val;
        lazy[id] += val;
    }
    void push(int id){
        if (lazy[id]){
        	add(id * 2, lazy[id]);
	    	add(id * 2 + 1, lazy[id]);
        	lazy[id] = 0;
		}
    }
    void upd(int id, int l, int r, int u, int v, int val){
        if (r < u || l > v) return;

        if (u <= l && r <= v){
			add(id, val);
			return;
		}

        push(id);

        int mid = (l + r) / 2;
        upd(id * 2, l, mid, u, v, val);
        upd(id * 2 + 1, mid + 1, r, u, v, val);
        st[id] = min(st[id * 2], st[id * 2 + 1]);
    }

    int get(int id, int l, int r, int u, int v){
        if (r < u || l > v) return 1e18;

        if (u <= l && r <= v) return st[id];

        push(id);

        int mid = (l + r) / 2;
        return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
    }
} tree;

void solve(){
	int n, d; cin >> n >> d;

	vector<int> compress;

    for (int i = 1; i <= n; i++){
		int x, a, bb; cin >> x >> a >> bb;
        b[i] = {bb, x, a};
        compress.emplace_back(x);
    }

    sort(compress.begin(), compress.end());
    compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
    sort(b + 1, b + n + 1, greater<>());

    set<pair<int, int>> s;
    s.insert({0, 0});
    s.insert({n + 1, d});
    tree.upd(1, 0, n, 1, n, d);
    int ans = d;
    b[0][0] = d;
    for (int i = 1; i <= n; i++){
        int pos = upper_bound(compress.begin(), compress.end(), b[i][1]) - compress.begin();
        auto it = s.lower_bound({pos, b[i][1]});
        tree.upd(1, 0, n, 0, n, b[i][0] - b[i - 1][0]);
        tree.upd(1, 0, n, pos, n, b[i][2]);
        if ((*it).first != pos){
        	int id_pre = (*prev(it)).first;
            int pos_nxt = (*it).second;

            tree.upd(1, 0, n, id_pre, id_pre, pos_nxt - b[i][1]);
            tree.upd(1, 0, n, pos, pos, -pos_nxt);
        }
        s.insert({pos, b[i][1]});
		int k = tree.get(1, 0, n, 0, n);
	    if(k >= 0) ans = min(ans, b[i][0] - k);

    }
    cout << ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

	solve();
}

• 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