Submission #266950

#	Time	Username	Problem	Language	Result	Execution time	Memory
266950		REALITYNB	Fuel Station (NOI20_fuelstation)	C++14	13 / 100	422 ms	55740 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 ; 
            vector<pii> tot ; 
            for(auto x : s){
                vector<pii> v = x.S ; 
                for(pii y : v) {
                    tot.push_back(y); 
                }
            }
            sort(tot.begin(),tot.end()) ; 
            for(pii& x : tot) d.push_back(x.F) ; 
            for(pii& x : tot) f.push_back(x.S) ; 
            d.push_back(D) ; 
            f.push_back(0) ; 
            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:26: 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