oj.uz

Submission #1040057

# Submission time Handle Problem Language Result Execution time Memory
1040057 2024-07-31T14:55:58 Z codexistent Schools (IZhO13_school) C++14
25 / 100
 609 ms 61536 KB 
#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
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 39004 KB Output is correct
2 Correct 12 ms 39376 KB Output is correct
3 Correct 14 ms 39256 KB Output is correct
4 Correct 16 ms 39260 KB Output is correct
5 Incorrect 15 ms 39256 KB Output isn't correct
6 Incorrect 12 ms 39260 KB Output isn't correct
7 Incorrect 16 ms 39740 KB Output isn't correct
8 Incorrect 22 ms 39772 KB Output isn't correct
9 Incorrect 22 ms 39768 KB Output isn't correct
10 Incorrect 23 ms 39800 KB Output isn't correct
11 Incorrect 19 ms 39772 KB Output isn't correct
12 Incorrect 16 ms 39900 KB Output isn't correct
13 Incorrect 98 ms 41796 KB Output isn't correct
14 Incorrect 98 ms 44596 KB Output isn't correct
15 Correct 152 ms 50968 KB Output is correct
16 Incorrect 278 ms 52496 KB Output isn't correct
17 Incorrect 472 ms 55676 KB Output isn't correct
18 Incorrect 483 ms 57300 KB Output isn't correct
19 Incorrect 543 ms 58640 KB Output isn't correct
20 Incorrect 609 ms 61536 KB Output isn't correct