Submission #1040060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040060		codexistent	Schools (IZhO13_school)	C++14	15 / 100	574 ms	61432 KiB

school

#include <bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define ll long long
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second

ll n, c[2], ans = 0;
pair<ll, ll> sc[MAXN];
vector<pair<pair<ll, ll>, ll>> ssc[2];
ll st[4][MAXN * 4], r[2][MAXN];

void update(ll i, ll l, ll r, ll updi, ll updv, ll stn){
    if(updi < l|| r < updi) return;

    if(l == r){
        st[stn][i] += updv;
        return;
    }
    update(i * 2, l, (l + r) / 2, updi, updv, stn);
    update(i * 2 + 1, (l + r) / 2 + 1, r, updi, updv, stn);

    st[stn][i] = st[stn][i * 2] + st[stn][i * 2 + 1];
}

ll query(ll i, ll l, ll r, pair<ll, ll> rng, ll stn){
    if(rng.s < l || r < rng.f) return 0;
    
    if(rng.f <= l && r <= rng.s) {
        return st[stn][i];
    }

    return query(i * 2, l, (l + r) / 2, rng, stn) + query(i * 2 + 1, (l + r) / 2 + 1, r, rng, stn);
}

int main(){
    cin >> n >> c[0] >> c[1];
    FOR(i, 0, 3) FOR(j, 0, MAXN * 4 - 1) st[i][j] = 0;
    FOR(i, 1, n){
        cin >> sc[i].f >> sc[i].s;
        ssc[0].push_back({{sc[i].f, sc[i].s}, i});
        ssc[1].push_back({{sc[i].s, sc[i].f}, i});
    }
    sort(ssc[0].begin(), ssc[0].end());
    sort(ssc[1].begin(), ssc[1].end());
    FOR(i, 1, n) r[0][ssc[0][i - 1].s] = i, r[1][ssc[1][i - 1].s] = i;

    FOR(t, 0, 1){
        FOR(i, 1, n){
            update(1, 1, n + 1, i, 1, t);
            update(1, 1, n + 1, i, ssc[t][i - 1].f.f, t + 2);
        }
    }

    FOR(i, 1, c[1]){
        update(1, 1, n + 1, r[0][ssc[1][ssc[1].size() - i].s], -1, 0);
        update(1, 1, n + 1, r[0][ssc[1][ssc[1].size() - i].s], -ssc[1][ssc[1].size() - i].f.s, 2);
    }

    FOR(i, 0, c[0]){
        if(i != 0){
            int rc = ssc[0][ssc[0].size() - i].s;
            if(query(1, 1, n + 1, {r[0][rc], r[0][rc]}, 0) == 0){
                update(1, 1, n + 1, r[0][rc], 1, 0);
                update(1, 1, n + 1, r[0][rc], sc[rc].f, 2);
            }
            if(query(1, 1, n + 1, {r[1][rc], r[1][rc]}, 1) == 1){
                update(1, 1, n + 1, r[1][rc], -1, 1);
                update(1, 1, n + 1, r[1][rc], -sc[rc].s, 3);
            }
        }

        ll sm = 0;

        ll a = 1, b = n + 1;
        while(a < b){
            ll m = (a + b + 1) / 2;
            if(query(1, 1, n + 1, {m, n + 1}, 0) >= c[0]){
                a = m;
            }else{
                b = m - 1;
            }
        }
        sm = query(1, 1, n + 1, {a, n}, 2);

        a = 1, b = n + 1 ;
        while(a < b){
            ll m = (a + b + 1) / 2;
            if(query(1, 1, n + 1, {m, n + 1}, 1) >= c[1]){
                a = m;
            }else{
                b = m - 1;
            }
        }
        ans = max(ans, sm + query(1, 1, n + 1, {a, n + 1}, 3));
    }

    cout << ans << endl;
}

• Subtask 1: 15 / 100