Submission #294550

#	Time	Username	Problem	Language	Result	Execution time	Memory
294550		nandonathaniel	Fuel Station (NOI20_fuelstation)	C++14	100 / 100	949 ms	40148 KiB

FuelStation

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=3e5+5,INF=1e18;

struct pom{
	LL x,a,b;
};

pom arr[MAXN];
LL tree[4*MAXN],lazy[4*MAXN],nxt[MAXN];

bool cmp(pom p,pom q){
	return p.x<q.x;
}

void updatenode(LL now,LL L,LL R,LL val){
	tree[now]+=val;
	lazy[now]+=val;
}

void pushdown(LL now,LL L,LL R){
	LL mid=(L+R)/2;
	updatenode(2*now,L,mid,lazy[now]);
	updatenode(2*now+1,mid+1,R,lazy[now]);
	lazy[now]=0;
}

LL query(LL now,LL L,LL R,LL x,LL y){
	if(L>=x && R<=y)return tree[now];
	if(L>y || R<x)return INF;
	pushdown(now,L,R);
	LL mid=(L+R)/2;
	return min(query(2*now,L,mid,x,y),query(2*now+1,mid+1,R,x,y));
}

void update(LL now,LL L,LL R,LL x,LL y,LL val){
	if(L>=x && R<=y){
		updatenode(now,L,R,val);
		return;
	}
	if(L>y || R<x)return;
	LL mid=(L+R)/2;
	pushdown(now,L,R);
	update(2*now,L,mid,x,y,val);
	update(2*now+1,mid+1,R,x,y,val);
	tree[now]=min(tree[2*now],tree[2*now+1]);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	LL n,d,idx=1;
	cin >> n >> d;
	for(LL i=1;i<=n;i++)cin >> arr[i].x >> arr[i].a >> arr[i].b;
	n++;
	arr[n].x=d;arr[n].a=0;arr[n].b=d;
	sort(arr+1,arr+n+1,cmp);
	for(LL i=1;i<=n;i++){
		if(arr[i].x!=arr[i-1].x){
			for(LL j=idx;j<i;j++)nxt[j]=i;
			idx=i;
		}
	}
	nxt[n]=n;
	vector<pii> v;
	for(LL i=1;i<=n;i++)v.push_back({arr[i].b,i});
	sort(v.begin(),v.end());
	//Frem=F-Xi+Sigma(Aj)
	//           Xj<Xi,F<=Bj
	for(auto isi : v){
		update(1,1,n,isi.second,isi.second,-arr[isi.second].x);  //-X[i]
		//Frem bisa dapet benefit A[j] ketika X[j]<X[i]
		update(1,1,n,nxt[isi.second],n,arr[isi.second].a); //Karena awal coba F=min(B[i]) maka semua pom bensin bisa
	}
	LL bef=0;
	idx=0;
	for(LL i=0;i<v.size();i++){
		//Try F=v[i].first
		update(1,1,n,1,n,v[i].first-bef);
		if(i>0 && v[i].first!=bef){
			for(LL j=idx;j<i;j++)update(1,1,n,nxt[v[j].second],n,-arr[v[j].second].a);    //F semakin besar pom yang bisa berbenefit semakin sedikit
			idx=i;
		}
		bef=v[i].first;
		LL minfrem=query(1,1,n,1,n);
		if(minfrem>=0){
			cout << v[i].first-minfrem << '\n';
			return 0;
		}
	}
	return 0;
}

Compilation message (stderr)

FuelStation.cpp: In function 'int main()':
FuelStation.cpp:78:14: warning: comparison of integer expressions of different signedness: 'LL' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(LL i=0;i<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