oj.uz

Submission #266914

# Submission time Handle Problem Language Result Execution time Memory
266914 2020-08-15T14:14:47 Z REALITYNB Fuel Station (NOI20_fuelstation) C++14
13 / 100
 474 ms 53020 KB 
    #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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 52896 KB Output is correct
2 Correct 349 ms 52932 KB Output is correct
3 Correct 416 ms 52852 KB Output is correct
4 Correct 392 ms 52860 KB Output is correct
5 Correct 400 ms 52840 KB Output is correct
6 Correct 395 ms 52904 KB Output is correct
7 Correct 390 ms 52856 KB Output is correct
8 Correct 474 ms 52924 KB Output is correct
9 Correct 403 ms 53020 KB Output is correct
10 Correct 351 ms 52896 KB Output is correct
11 Correct 381 ms 52936 KB Output is correct
12 Correct 341 ms 52836 KB Output is correct
13 Correct 386 ms 52876 KB Output is correct
14 Correct 388 ms 52896 KB Output is correct
15 Correct 452 ms 52844 KB Output is correct
16 Correct 345 ms 52896 KB Output is correct
17 Correct 379 ms 52940 KB Output is correct
18 Correct 377 ms 52872 KB Output is correct
19 Correct 384 ms 52896 KB Output is correct
20 Correct 355 ms 52892 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -