Submission #266844

#	Time	Username	Problem	Language	Result	Execution time	Memory
266844		REALITYNB	Fuel Station (NOI20_fuelstation)	C++14	20 / 100	1082 ms	61988 KiB

FuelStation

#include <bits/stdc++.h> 
#define pii pair<int,int> 
#define F first 
#define int long long 
#define S second 
#define mp make_pair
using namespace std; 
bool check(int s , vector<int>& d , vector<int>& f){
    int li = 0 , rest = s ; 
    for(int i=0;i<d.size();i++){
        if(d[i]-li>rest) return 0 ; 
        rest -= (d[i]-li) ;
        rest+=f[i] ; 
        li = d[i] ; 
    }
    return 1 ; 
}
int bs(int lw , int ur , int D , map<int,vector<pii>> s){
    int l =  lw , r = ur ; 
    vector<int> d , f ; 
    for(auto x : s){
        vector<pii> v = x.S ; 
        for(pii y : v) {
            d.push_back(y.F) ;  
            f.push_back(y.S) ; 
        }
    }
    d.push_back(D) ; 
    while(r-l-1){
        int md = (r+l)/2 ;
        if(check(md,d,f)){
            r= md ; 
        }
        else l = md  ; 
    }
    return r ; 
}
signed main(){
	int n ,D; 
	cin>>n>>D ;
	//a[i] -> how much fuel he can get in the ith station 
	//b[i] -> F <= b[i] condition 
	//d[i] -> distance from start 
	//d  -> finish line
	map<int,vector<pii>> s ; 
	for(int i=0;i<n;i++){
		int f , b,d ; 
		cin>>d>>f>>b ; 
		s[b].push_back(mp(d,f)) ;  
	}
	for(auto x : s){
		vector<pii> v = x.S  ;  
		sort(v.begin(),v.end()) ; 
		s[x.F]= v ; 
	}
	multiset<int> r ; 
	multiset<pii> ur ; 
	int rest = 0  , li =  0 ; 
	r.insert(0) ; 
	ur.insert(mp(D,0)) ; 
	for(auto x : s){
		int F = x.F ; 
		vector<pii> fs = x.S ; 
		for(pii y : fs) ur.insert(y) ; 
		rest+= F-li   ; 
		auto it = r.end() ; 
		it-- ; 
		int big = *it ; 
		while(big>=(*(ur.begin())).F){
			rest+=(*ur.begin()).S  ; 
			r.insert((*ur.begin()).F) ;  
			ur.erase(ur.begin()) ; 
		}
		while(ur.size()&&(*ur.begin()).F-big<=rest){
			r.insert((*ur.begin()).F) ; 
			rest+= (*ur.begin()).S ;
			rest-= ((*ur.begin()).F-big) ; 
		    big = (*ur.begin()).F ; 
			ur.erase(ur.begin()) ; 
		}
		if(ur.empty()){
			cout << bs(li,F,D,s) ; 
			return 0 ;  
		}	
		li = F ; 
	}
	cout << D  ; 
	return 0 ; 
}

Compilation message (stderr)

FuelStation.cpp: In function 'bool check(long long int, std::vector<long long int>&, std::vector<long long int>&)':
FuelStation.cpp:10:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0;i<d.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 12
• Subtask 5: 0 / 19
• Subtask 6: 0 / 11
• Subtask 7: 0 / 21