oj.uz

Submission #266950

# Submission time Handle Problem Language Result Execution time Memory
266950 2020-08-15T14:30:34 Z REALITYNB Fuel Station (NOI20_fuelstation) C++14
13 / 100
 422 ms 55740 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 ; 
            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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Incorrect 1 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 55560 KB Output is correct
2 Correct 364 ms 55548 KB Output is correct
3 Correct 381 ms 55532 KB Output is correct
4 Correct 403 ms 55644 KB Output is correct
5 Correct 422 ms 55540 KB Output is correct
6 Correct 351 ms 55548 KB Output is correct
7 Correct 397 ms 55540 KB Output is correct
8 Correct 361 ms 55556 KB Output is correct
9 Correct 390 ms 55552 KB Output is correct
10 Correct 371 ms 55596 KB Output is correct
11 Correct 415 ms 55584 KB Output is correct
12 Correct 382 ms 55612 KB Output is correct
13 Correct 388 ms 55576 KB Output is correct
14 Correct 357 ms 55584 KB Output is correct
15 Correct 403 ms 55740 KB Output is correct
16 Correct 420 ms 55584 KB Output is correct
17 Correct 344 ms 55580 KB Output is correct
18 Correct 349 ms 55608 KB Output is correct
19 Correct 345 ms 55584 KB Output is correct
20 Correct 370 ms 55644 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 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 288 KB Output is correct
2 Incorrect 1 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 288 KB Output is correct
2 Incorrect 1 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 288 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -