# CFR 738 C. Road to Cinema ( Binary Search )

Problem - C - Codeforces

n: 車的數量, k: 加油站數量, s: 終點, t: 目標時間
1 ≤ n ≤ 2e5, 1 ≤ k ≤ 2e5, 2 ≤ s ≤ 1e9, 1 ≤ t ≤ 2e9
ci: 第 i 個車的價格, vi: 第 i 個車的油箱容量
1 ≤ ci, vi ≤ 1e9
gi: 第 i 個加油站位置
1 ≤ gi ≤ s - 1

O( K lg K + K lg N )

```int N, K, S, T;
vp CV;
vi G;

void init(){
cin >> N >> K >> S >> T;
CV = vp( N );
for( int i = 0; i < N; ++i )
cin >> CV[ i ].first >> CV[ i ].second;
G = vi( K );
for( int i = 0; i < K; ++i )
cin >> G[ i ];
}

vp cv;

bool cmp( const pii a, const pii b ){
if( a.first != b.first )
return a.first < b.first;
return a.second > b.second;
}

void preprocess(){
sort( CV.begin(), CV.end(), cmp );
cv.emplace_back( CV[ 0 ] );
for( int i = 1; i < N; ++i )
if( CV[ i ].second > cv.back().second )
cv.emplace_back( CV[ i ] );
sort( G.begin(), G.end() );
}

int ok( int x ){
int t = 0;
int lp = 0;
for( int i = 0; i < G.size(); ++i ){ // gas - 2a ≥ d - a, gas - d ≥ a
int d = G[ i ] - lp;
if( cv[ x ].second < d )
return 0;
int a = min( d, ( cv[ x ].second - d ) );
int b = d - a;
t += a + 2 * b;
lp = G[ i ];
}
int d = S - G.back();
if( cv[ x ].second < d )
return 0;
int a = min( d, ( cv[ x ].second - d ) );
int b = d - a;
t += a + 2 * b;
return t <= T;
}

void solve(){
for( int i = 1; i < cv.size(); ++i )
assert( cv[ i ].first > cv[ i - 1 ].first and cv[ i ].second > cv[ i - 1 ].second );
int ans = -1;
int lb = 0, rb = cv.size() - 1;
while( lb <= rb ){
int mid = lb + rb >> 1;
if( ok( mid ) )
ans = mid, rb = mid - 1;
else
lb = mid + 1;
}
if( ans == -1 )
cout << -1 << endl;
else
cout << cv[ ans ].first << endl;
}
```