Submission #333010

#	Time	Username	Problem	Language	Result	Execution time	Memory
333010		Cantfindme	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	728 ms	56336 KiB

FuelStation

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 300010;
typedef pair<int,pi> pii;
#define p(x,y,z) pii(x,pi(y,z))

const int INF = LLONG_MAX/2;

int n,d;
vector <pii> v; //Bi, pos, Ai
vector <int> posv;

struct node {
	int s,m,e,v, lazy;
	node *l, *r;
	node(int _s, int _e) {
		s = _s; e = _e; m = (s+e)/2;
		v = lazy = 0;
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	
	void push() {
		if (lazy == 0) return;
		v += lazy;
		if (s != e) {
			l -> lazy += lazy;
			r -> lazy += lazy;
		}
		lazy = 0;
	}
	
	void up(int x, int y, int newv) {
		if (s == x and e == y) lazy += newv;
		else {
			if (x > m) r -> up(x,y,newv);
			else if (y <= m) l -> up(x,y,newv);
			else l -> up(x,m,newv), r -> up(m+1,y,newv);
			l -> push(); 
			r -> push();
			v = min(l -> v, r -> v);
		}
	}
	
	int rmq() {
		push();
		return v;
	}
}*root;

int32_t main() {
	FAST
	cin >> n >> d;
	for (int i =0;i<n;i++) {
		int pos,a,b; cin >> pos >> a >> b;
		v.push_back(p(b,pos,a));
		posv.push_back(pos);
	}
	v.push_back(p(d,d,0));
	posv.push_back(d);
	root = new node(0,n);
	//cout << "HELLO\n";
	
	sort(v.rbegin(),v.rend());
	sort(posv.begin(),posv.end());
	
	for (int i =0;i<=n;i++) {
		//cout << i << "\n";
		root -> up(i,i,-posv[i]);
	}
	
	int prevf = 0;
	int ans = INF;
	for (int i =0;i<(int)v.size();i++) {
		int curf = v[i].f, x = v[i].s.f, ai = v[i].s.s;
		
		//cout << "NEW: " << curf << " " << x << " " << ai << "\n";
		root -> up(0ll,n, (curf - prevf));
		int indx = lower_bound(posv.begin(),posv.end(),x) - posv.begin();
		
		if (indx+1 <= n) root -> up(indx+1,n,ai);
		
		int extra = root -> rmq();
		if (extra >= 0) {
			ans = min(ans, curf - extra); 
		}
	
		prevf = curf;
	}
	cout << ans;
}

• 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