Submission #903843

#	Time	Username	Problem	Language	Result	Execution time	Memory
903843		pcc	Fuel Station (NOI20_fuelstation)	C++14	100 / 100	512 ms	59964 KiB

FuelStation

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define ls (now*2+1)
#define rs (now*2+2)
#define mid ((l+r)>>1)


const int mxn = 3e5+10;
ll N,L;
pll segtree[mxn*12];
pair<ll,pll> arr[mxn];
vector<pll> v;
vector<int> all;

void modify(int now,int l,int r,int s,int e,ll v){
	if(l>=s&&e>=r){
		segtree[now].sc += v;
		return;
	}
	if(mid>=s)modify(now*2+1,l,mid,s,e,v);
	if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
	segtree[now].fs = min(segtree[ls].fs+segtree[ls].sc,segtree[rs].fs+segtree[rs].sc);
}


int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>L;
	for(int i = 1;i<=N;i++){
		cin>>arr[i].fs>>arr[i].sc.fs>>arr[i].sc.sc;
		v.push_back(make_pair(arr[i].sc.sc,i));
		all.push_back(arr[i].fs);
		all.push_back(arr[i].fs+1);
		if(arr[i].fs-1>0)all.push_back(arr[i].fs-1);
	}
	all.push_back(0);
	all.push_back(L);
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	while(all.back()>L)all.pop_back();
	ll len = all.size();
	for(int i = 0;i<len;i++){
		modify(0,0,len,i,i,-all[i]);
	}
	ll ans = L;
	sort(v.rbegin(),v.rend());
	v.push_back(make_pair(0,0));
	//for(auto &i:all)cout<<i<<',';cout<<endl;
	for(int i = 0;i+1<v.size();i++){
		int now = v[i].sc;
		int p = lower_bound(all.begin(),all.end(),arr[now].fs)-all.begin();
		modify(0,0,len,p+1,len,arr[now].sc.fs);
		ll tans = max(-(segtree[0].fs+segtree[0].sc),v[i+1].fs);
		//cout<<v[i].fs<<":"<<now<<","<<p<<" "<<tans<<endl;
		if(v[i].fs>=tans)ans = min(ans,tans);
	}
	cout<<ans;
}

Compilation message (stderr)

FuelStation.cpp: In function 'int main()':
FuelStation.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0;i+1<v.size();i++){
      |                ~~~^~~~~~~~~

• 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