oj.uz

Submission #1040060

# Submission time Handle Problem Language Result Execution time Memory
1040060 2024-07-31T15:02:50 Z codexistent Schools (IZhO13_school) C++14
15 / 100
 574 ms 61432 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
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 37980 KB Output isn't correct
2 Correct 14 ms 37976 KB Output is correct
3 Correct 13 ms 37980 KB Output is correct
4 Incorrect 13 ms 37976 KB Output isn't correct
5 Incorrect 12 ms 37912 KB Output isn't correct
6 Incorrect 13 ms 37980 KB Output isn't correct
7 Incorrect 17 ms 38460 KB Output isn't correct
8 Incorrect 24 ms 38436 KB Output isn't correct
9 Incorrect 22 ms 38460 KB Output isn't correct
10 Incorrect 20 ms 38440 KB Output isn't correct
11 Incorrect 17 ms 38460 KB Output isn't correct
12 Incorrect 17 ms 38436 KB Output isn't correct
13 Incorrect 97 ms 40764 KB Output isn't correct
14 Incorrect 100 ms 44148 KB Output isn't correct
15 Correct 147 ms 50476 KB Output is correct
16 Incorrect 269 ms 51980 KB Output isn't correct
17 Incorrect 464 ms 55060 KB Output isn't correct
18 Incorrect 480 ms 56848 KB Output isn't correct
19 Incorrect 508 ms 58384 KB Output isn't correct
20 Incorrect 574 ms 61432 KB Output isn't correct