제출 #1291378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291378		samarthkulkarni	Fuel Station (NOI20_fuelstation)	C++20	54 / 100	6 ms	856 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 = 1e4+10;


#define pr pair<ll, ll>  
#define ff first
#define ss second


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];

const ll inf = 1e18;


/*
	if f <= Bi <= Bj
	then I should collet Ai and Aj
*/


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; 
	}

	a[n].X = d;
	a[n].A = 0;
	a[n].B = inf;
	n++;

	sort(a, a+n);
	

	vi b = {0};
	for (int i = 0; i < n; i++) b.push_back(a[i].B);

	sort(all(b));	
	b.erase(unique(all(b)), b.end());



	auto isValid = [&](ll f) {
		ll curr = f;
		ll p = 0;

		bool flag = true;
		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 {
				flag = false; break;
			}
		}
		return flag;
	};

	ll ans = inf;
	for (int i = 1; i < b.size(); i++) {

		if (!isValid(b[i])) continue;

		ll p = b[i-1]+1;
		ll q = b[i];

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

		break;
	}

	cout << ans << endl;



}

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