Submission #266914

#	Time	Username	Problem	Language	Result	Execution time	Memory
266914		REALITYNB	Fuel Station (NOI20_fuelstation)	C++14	13 / 100	474 ms	53020 KiB

FuelStation

    #include <bits/stdc++.h> 
    #define int long long 
    #define pii pair<long long,long long> 
    #define F first 
    #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(){
    	ios_base::sync_with_stdio(0) ; 
    	cin.tie(0) ; 
    	cout.tie(0) ; 
    	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 << bs(li,D,D,s)  ; 
    	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:22: 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: 0 / 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