Submission #676488

#	Time	Username	Problem	Language	Result	Execution time	Memory
676488		penguin133	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	1239 ms	72864 KiB

FuelStation

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
pair<int, pii> A[300005];
pii B[300005];
int exis[300005];
struct node{
	int s,e,m,val, lazy;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = 0;
		lazy = 0;
		if(s != e){
			l = new node(s, m);
			r=  new node(m+1, e);
		} 
	}
	void propo(){
		if(lazy){
			val += lazy;
			if(s != e){
				l->lazy += lazy;
				r->lazy += lazy;
			}
			lazy = 0;
		}
	}
	void update(int a, int b, int c){
		if(a == s && b == e)lazy += c;
		else{
			if(b <= m)l->update(a,b,c);
			else if(a > m)r->update(a,b,c);
			else l->update(a,m,c), r->update(m+1,b,c);
			l->propo(), r->propo();
			val = min(l->val, r->val);
		}
	}
	int query(int p){
		propo();
		if(s == e)return val;
		if(p <= m)return l->query(p);
		else return r->query(p);
	}
}*root;
main(){
	int n,d;cin >> n >> d;
	root = new node(0, n+ 5);
	for(int i=1;i<=n;i++){
		cin >> A[i].first >> A[i].second.first >> A[i].second.second;
	}
	sort(A+1, A+n+1);
	A[n+1] = {d,{0,0}};
	for(int i=1;i<=n;i++)B[i] = {A[i].second.second, i};
	sort(B+1, B+n+1);
	int in = n ;
	exis[0] = exis[n+1] = true;
	multiset<int>s;
	s.insert(0);
	s.insert(n+1);
	root->update(0,0,0);
	root->update(n+1,n+1,-d);
	int cnt = d;
	while(in >= 1){
		int x = B[in].first;
		while(B[in].first == x){
			int y = B[in].second;
			multiset<int> :: iterator it = s.upper_bound(y);
			it--;
			int temp = root->query(*it);
			root->update(y,y,temp + A[*it].first - A[y].first + A[*it].second.first);
			root->update(y+1,n+1,A[y].second.first); 
			s.insert(y);
			in--;
		}
		root->propo();
		int mini = root->val;
		mini = -mini;
		if(mini <= x)cnt = min(cnt, mini);
	}
	cout << cnt;
}

Compilation message (stderr)

FuelStation.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~

• 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