oj.uz

Submission #266911

# Submission time Handle Problem Language Result Execution time Memory
266911 2020-08-15T14:12:34 Z REALITYNB Fuel Station (NOI20_fuelstation) C++14
13 / 100
 447 ms 56604 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: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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 429 ms 56308 KB Output is correct
2 Correct 428 ms 56360 KB Output is correct
3 Correct 395 ms 56312 KB Output is correct
4 Correct 409 ms 56312 KB Output is correct
5 Correct 417 ms 56276 KB Output is correct
6 Correct 447 ms 56604 KB Output is correct
7 Correct 391 ms 56284 KB Output is correct
8 Correct 414 ms 56268 KB Output is correct
9 Correct 432 ms 56276 KB Output is correct
10 Correct 393 ms 56376 KB Output is correct
11 Correct 379 ms 56352 KB Output is correct
12 Correct 372 ms 56280 KB Output is correct
13 Correct 420 ms 56308 KB Output is correct
14 Correct 444 ms 56388 KB Output is correct
15 Correct 368 ms 56272 KB Output is correct
16 Correct 370 ms 56304 KB Output is correct
17 Correct 435 ms 56360 KB Output is correct
18 Correct 446 ms 56300 KB Output is correct
19 Correct 427 ms 56296 KB Output is correct
20 Correct 405 ms 56280 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 384 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 384 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 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -