제출 #1313007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313007		hectormedrano	Hiring (IOI09_hiring)	C++20	0 / 100	1598 ms	51140 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct can{
    ll ind, q, s, pos;
};

vector<can> c;

bool ord1(can x, can y){
    return (x.q < y.q);
}

bool ord2(can x, can y){
    return ((x.s)*(y.q) > (y.s)*(x.q));
}

vector<pair<ll, ll>> st;
vector<ll> a;

pair<ll, ll> operator +(pair<ll, ll> d1, pair<ll, ll> d2){
    return {d1.first + d2.first, d1.second + d2.second};
}

void update(ll l, ll r, ll id, ll pos, ll val){
    if(l==r){
        st[id].first = 1;
        st[id].second = val;
        return;
    }
    ll m = (l+r)/2;
    if(pos<=m){update(l, m, 2*id, pos, val);}
    else{update(m+1, r, 2*id+1, pos, val);}
    st[id] = st[2*id] + st[2*id+1];
}

pair<ll, ll> query(ll l, ll r, ll id, ll ql, ll qr){
    if(r<ql or qr<l){return {0, 0};}
    if(ql<=l and r<=qr){return st[id];}
    ll m = (l+r)/2;
    return query(l, m, 2*id, ql, qr) + query(m+1, r, 2*id+1, ql, qr);
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    ll N, W, ans;
    cin>>N>>W;
    c.resize(N);
    st.resize(4*N+13, {0, 0});
    a.resize(N+2, 0);
    a[N+1] = 1e15;
    for(ll i=0;i<N;i++){
        c[i].ind = i;
        cin>>c[i].s>>c[i].q;
    }
    sort(c.begin(), c.end(), ord1);
    for(ll i=0;i<N;i++){
        c[i].pos = i;
    }
    sort(c.begin(), c.end(), ord2);
    ans = 0;
    for(ll i=N-1;i>=0;i--){
        ll T = max(0LL, (W*(c[i].q))/c[i].s - c[i].q);
        ll bl = 0;
        ll br = N+1;
        while(br != bl+1){
            ll bm = (bl + br)/2;
            pair<ll, ll> d = query(0, N+1, 1, 0, bm);
            if(d.second <= T){bl = bm;}
            else{br = bm;}
        }
        ll mx = query(0, N+1, 1, 0, bl).first;
        ans = max(ans, mx + 1);
        update(0, N+1, 1, c[i].pos + 1, c[i].q);
    }
    cout<<ans<<endl;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 28
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6