CFR Educational 3 D. Gadgets for dollars and pounds ( Binary search )

Problem - D - Codeforces
If a bound is set, i.e. to construct a way to buy k gadgets before some day x, we have an obvious greedy strategy where we will choose the cheapest currency days for both currency, then we will enumerate the number of gadgets we will buy with dollars and the others will have to be bought with pounds, where of course the gadgets will be sorted according to their costs. The time complexity for checking whether it is possible is O( m ), so the overall complexity is O( m lg n ).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
const int MAXM = 2e5 + 5;
const int MAXK = MAXM;
const int MAXS = 1e9 + 9;

struct Toy{
    int id, cost;
    Toy(int _i = 0, int _c = 0): id( _i ), cost( _c ){}
    bool operator < (const Toy &oth) const{
        return cost < oth.cost;
    }
} toy;

int n, m, k, s;

int a[ MAXN ], b[ MAXN ];
int pa[ MAXN ], pb[ MAXN ]; // prefix min
int minda[ MAXN ], mindb[ MAXN ]; // when is that min

vector<Toy> toy1, toy2;
ll pt1[ MAXM ], pt2[ MAXM ]; // prefix sum

bool ok(int day, bool show = false){
    for(int b1 = 0; b1 <= toy1.size() - 1; ++b1){ // buy how much toy1
        int b2 = k - b1; if( b2 < 0 || b2 > toy2.size() - 1 ) continue;
        if( pa[ day ] * pt1[ b1 ] + pb[ day ] * pt2[ b2 ] <= s ){
            if( show ){
                for(int i = 1; i <= b1; ++i)
                    printf("%d %d\n", toy1[ i ].id, minda[ day ]);
                for(int i = 1; i <= b2; ++i)
                    printf("%d %d\n", toy2[ i ].id, mindb[ day ]);
            }
            return true;
        }
    }
    return false;
}

void solve(){
    pa[ 1 ] = a[ 1 ], pb[ 1 ] = b[ 1 ];
    minda[ 1 ] = mindb[ 1 ] = 1;
    for(int i = 2; i <= n; ++i){
        if( a[ i ] < pa[ i - 1 ] ) minda[ i ] = i;
        else minda[ i ] = minda[ i - 1 ];
        if( b[ i ] < pb[ i - 1 ] ) mindb[ i ] = i;
        else mindb[ i ] = mindb[ i - 1 ];
        pa[ i ] = min<int>( pa[ i - 1 ], a[ i ] );
        pb[ i ] = min<int>( pb[ i - 1 ], b[ i ] );
    }
    sort( toy1.begin(), toy1.end() );
    sort( toy2.begin(), toy2.end() );
    for(int i = 1; i < toy1.size(); ++i)
        pt1[ i ] = pt1[ i - 1 ] + toy1[ i ].cost;
    for(int i = 1; i < toy2.size(); ++i)
        pt2[ i ] = pt2[ i - 1 ] + toy2[ i ].cost;
    
    int ans = -1;
    int lb = 1, rb = n;
    while( lb <= rb ){
        int mid = ( lb + rb ) / 2;
        if( ok( mid ) ) ans = mid, rb = mid - 1;
        else lb = mid + 1;
    }

    printf("%d\n", ans);
    if( ans > 0 ) ok( ans, true );
}

int main(){
    scanf("%d%d%d%d", &n, &m, &k, &s);
    for(int i = 1; i <= n; ++i) // 1 BASED IDX
        scanf("%d", &a[ i ]);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &b[ i ]);
    toy1.push_back( Toy() ); toy2.push_back( Toy() ); // sentinel
    for(int i = 1; i <= m; ++i){
        int t, c; scanf("%d%d", &t, &c);
        if( t == 1 ) toy1.push_back( Toy( i, c ) );
        else toy2.push_back( Toy( i, c ) );
    }
    solve();
    return 0;
}