Submission #1291325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291325		samarthkulkarni	Fuel Station (NOI20_fuelstation)	C++20	13 / 100	103 ms	7452 KiB

FuelStation

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

#define ll long long
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


const int MAXN = 3e5+10;
struct point {
	ll X, A, B;

	bool operator<(point temp) {
		if (X == temp.X) return B < temp.B;
		return X < temp.X;
	}
};

point a[MAXN];


void solution() {
	ll n, d; cin >> n >> d;

	for (int i = 0; i < n; i++) {
		cin >> a[i].X >> a[i].A >> a[i].B; 
	}

	sort(a, a+n);


	auto isValid = [&](ll F) {
		ll curr = F;
		ll p = 0;
		for (int i = 0; i < n; i++) {
			if (a[i].X - p <= curr) {
				curr -= (a[i].X - p);
				p = a[i].X;

				if (F <= a[i].B) {
					curr += a[i].A;
				}
			} else {
				return false;
			}
		}


		return d-p <= curr;
	};	




	ll p = 0, q = d;

	ll ans = d;
	while (p <= q) {
		ll mid = (p + q)/2;
		if (isValid(mid)) {
			ans = mid;	
			q = mid-1;
		} else p = mid+1;
	}

	cout << ans << endl;

	
}

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