# CFR 589 G. Hiring ( Segment Tree, Binary Search )

Problem - G - Codeforces

N, M ≤ 2e5
T, R ≤ 1e6
TL: 4000 ms
ML: 512 MB

O( N lg N + M lg M )

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = ( int ) 2e5;
const int MAXM = ( int ) 2e5;

int N, M;
int T[ MAXM ];
int D[ MAXN ], R[ MAXN ];
int ord_d[ MAXN ]; // sort by D large to small
int ord_t[ MAXM ]; // sort by R large to small
int ans[ MAXN ];

struct Segment_Tree{
ll sum[ MAXM << 3 ];
int cnt[ MAXM << 3 ];
void modify( int t, int lb, int rb, int k, int v ){
if( lb + 1 == rb ){
sum[ t ] = v;
cnt[ t ] = 1;
return;
}
int mid = lb + rb >> 1;
if( k < mid ) modify( t << 1, lb, mid, k, v );
else modify( t << 1 | 1, mid, rb, k, v );
sum[ t ] = sum[ t << 1 ] + sum[ t << 1 | 1 ];
cnt[ t ] = cnt[ t << 1 ] + cnt[ t << 1 | 1 ];
}
void dfs( int t, int lb, int rb, int s, int d, int &ans ){
if( lb + 1 == rb ){
if( s <= 0 ) return ( void ) ( ans = lb );
s -= sum[ t ] - cnt[ t ] * d;
if( s <= 0 ) return ( void ) ( ans = rb );
assert( rb == M );
return ( void ) ( ans = 0 );
}
int mid = lb + rb >> 1;
ll lft = sum[ t << 1 ] - 1LL * d * cnt[ t << 1 ];
if( s <= lft ) return dfs( t << 1, lb, mid, s, d, ans );
return dfs( t << 1 | 1, mid, rb, s - lft, d, ans );
}
} segt;

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < M; ++i ){
cin >> T[ i ];
ord_t[ i ] = i;
}
for( int i = 0; i < N; ++i ){
cin >> D[ i ] >> R[ i ];
ord_d[ i ] = i;
}
sort( ord_t, ord_t + M, [ & ]( int i, int j ){ return T[ i ] > T[ j ]; } );
sort( ord_d, ord_d + N, [ & ]( int i, int j ){ return D[ i ] > D[ j ]; } );
{
int ptr_ord_t = 0;
for( int i = 0; i < N; ++i ){
while( ptr_ord_t < M and T[ ord_t[ ptr_ord_t ] ] >= D[ ord_d[ i ] ] ){
segt.modify( 1, 0, M, ord_t[ ptr_ord_t ], T[ ord_t[ ptr_ord_t ] ] );
++ptr_ord_t;
}
segt.dfs( 1, 0, M, R[ ord_d[ i ] ], D[ ord_d[ i ] ], ans[ ord_d[ i ] ] );
}
}
for( int i = 0; i < N; ++i ){
cout << ans[ i ] << " \n"[ i + 1 == N ];
}
return 0;
}
```