Submission #500735

#	Time	Username	Problem	Language	Result	Execution time	Memory
500735		arujbansal	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	301 ms	41992 KiB

FuelStation

#include <bits/stdc++.h>

using namespace std;

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

const int MXN = 3e5 + 5, INF = 1e18;
int N, D;
int tree[4 * MXN], lazy[4 * MXN], tree_build[MXN];
array<int, 3> A[MXN];

int merge(int x, int y) {
	return min(x, y);
}

void build(int i, int l, int r) {
	if (l == r) {
		tree[i] = tree_build[l];
		return;
	}

	int mid = (l + r) / 2;
	build(2 * i, l, mid);
	build(2 * i + 1, mid + 1, r);
	tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}

void propagate(int i, int l, int r) {
	if (lazy[i] == 0) return;

	tree[i] += lazy[i];

	if (l != r) {
		lazy[2 * i] += lazy[i];
		lazy[2 * i + 1] += lazy[i];
	}

	lazy[i] = 0;
}

void increment(int i, int l, int r, int ql, int qr, int val) {
	propagate(i, l, r);
	if (l > qr || r < ql) return;
	if (l >= ql && r <= qr) {
		lazy[i] += val;
		propagate(i, l, r);
		return;
	}

	int mid = (l + r) / 2;
	increment(2 * i, l, mid, ql, qr, val);
	increment(2 * i + 1, mid + 1, r, ql, qr, val);
	tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}

int query(int i, int l, int r, int ql, int qr) {
	propagate(i, l, r);
	if (l > qr || r < ql) return INF;
	if (l >= ql && r <= qr) return tree[i];

	int mid = (l + r) / 2;
	return merge(query(2 * i, l, mid, ql, qr), query(2 * i + 1, mid + 1, r, ql, qr));
}

void increment(int l, int r, int val) { increment(1, 0, N - 1, l, r, val); }

int query(int l, int r) { return query(1, 0, N - 1, l, r); }

void deactivate(int idx, int nxt) {
	if (nxt > N - 1) return;
	increment(nxt, N - 1, -A[idx][1]);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> D;

	for (int i = 0; i < N; i++)
		cin >> A[i][0] >> A[i][1] >> A[i][2];

	sort(A, A + N);

	A[N] = {D, 0, D};
	N++;

	vector<pair<int, int>> sorted_b;
	int fuel_sum = 0;

	int ptr = 0;

	for (int i = 0; i < N; i++) {
		while (ptr < N && A[ptr][0] != A[i][0])
			fuel_sum += A[ptr++][1];

		tree_build[i] = -A[i][0] + fuel_sum;

		
		sorted_b.emplace_back(A[i][2], i);
	}

	build(1, 0, N - 1);
	sort(all(sorted_b));

	vector<int> nxt(N, N + 2);
	for (int i = 0, j = 0; i < N; i++) {
		for (; j < N && A[i][0] == A[j][0]; j++);

		// cout << j << "\n";

		nxt[i] = j;
		// cout << i << " " << nxt[i] << "\n";
		

		while (i < j)
			nxt[i++] = j;

		i--;

		// cout << i << " " << nxt[i] << "\n";
	}

	// cout << N << "\n";

	// for (int k = 0; k < N; k++)
	// 	cout << nxt[sorted_b[k].second] << " ";

	// cout << "\n\n";

	for (int i = 0, j = 0, last = 0; i < sz(sorted_b); i++) {
		increment(0, N - 1, sorted_b[i].first - last);
		last = sorted_b[i].first;

		while (j <= i && sorted_b[j].first < sorted_b[i].first) {
			deactivate(sorted_b[j].second, nxt[sorted_b[j].second]);
			j++;
		}

		// for (int k = 0; k < N; k++)
		// 	cout << query(k, k) << " ";

		// cout << "\n\n";

		int qry = query(0, N - 1);
		if (qry >= 0) {
			cout << sorted_b[i].first - qry;
			return 0;
		}
	}

	// cout << sorted_b.back().first;
}

/*
2 15
9 1 14
9 5 1
*/

• 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