Submission #261258

#	Time	Username	Problem	Language	Result	Execution time	Memory
261258		Berted	Fuel Station (NOI20_fuelstation)	C++14	100 / 100	2035 ms	45512 KiB

FuelStation

#include <iostream>
#include <algorithm>
#include <map>
#define ll long long
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second

using namespace std;

const int SZ = (1 << 20) + 69;

int n, d; 
ll coord[300069] = {}, seg[SZ] = {}, lz[SZ], rs = 1e18;
map<int, int> mp;
ppi dt[300069] = {};

void bld(int idx, int L, int R)
{
	if (L < R)
	{
		bld(2 * idx, L, (L + R) / 2);
		bld(2 * idx + 1, (L + R) / 2 + 1, R);
		seg[idx] = max(seg[2 * idx], seg[2 * idx + 1]);
	}
	else {seg[idx] = coord[L];}
}

void prop(int idx, int L, int R)
{
	if (lz[idx])
	{
		seg[idx] += lz[idx];
		if (L < R)
		{
			lz[2 * idx] += lz[idx];
			lz[2 * idx + 1] += lz[idx];
		}
		lz[idx] = 0;
	}
}

void upd(int idx, int L, int R, int x, int v)
{
	prop(idx, L, R);
	if (x <= R) 
	{
		if (x <= L) {lz[idx] += v; prop(idx, L, R);}
		else
		{
			int M = (L + R) / 2;
			upd(2 * idx, L, M, x, v);
			upd(2 * idx + 1, M + 1, R, x, v);
			seg[idx] = max(seg[2 * idx], seg[2 * idx + 1]);
		}
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> d;
	rs = d;
	for (int i = 0; i < n; i++)
	{
		int x, a, b; cin >> x >> a >> b;
		mp[x] = 1;
		dt[i] = {{b, x}, a};
	}
	mp[d] = 1;
	int it = 0;
	for (auto &x : mp)
	{
		coord[it] = x.fst;
		x.snd = it++;
	}
	bld(1, 0, it - 1);
	//cout << seg[1] << "\n";
	for (int i = 0; i < n; i++)
	{
		upd(1, 0, it - 1, mp[dt[i].fst.snd] + 1, -dt[i].snd);
	}
	sort(dt, dt + n);
	//cout << seg[1] << "\n";
	for (int i = 0; i < n; i++)
	{
		if (seg[1] <= dt[i].fst.fst) {rs = min(rs, seg[1]);}
		upd(1, 0, it - 1, mp[dt[i].fst.snd] + 1, dt[i].snd);
	}
	cout << rs << "\n";
	return 0;
}

• 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