oj.uz

Submission #1040053

# Submission time Handle Problem Language Result Execution time Memory
1040053 2024-07-31T14:49:09 Z codexistent Schools (IZhO13_school) C++14
20 / 100
 561 ms 64812 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, i, 1, t);
            update(1, 1, n, i, ssc[t][i - 1].f.f, t + 2);
        }
    }

    FOR(i, 1, c[1]){
        update(1, 1, n, r[0][ssc[1][ssc[1].size() - i].s], -1, 0);
        update(1, 1, n, 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, {r[0][rc], r[0][rc]}, 0) == 0){
                update(1, 1, n, r[0][rc], 1, 0);
                update(1, 1, n, r[0][rc], sc[rc].f, 2);
            }
            if(query(1, 1, n, {r[1][rc], r[1][rc]}, 1) == 1){
                update(1, 1, n, r[1][rc], -1, 1);
                update(1, 1, n, r[1][rc], -sc[rc].s, 3);
            }
        }

        ll sm = 0;

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

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

    cout << ans << endl;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37980 KB Output is correct
2 Incorrect 12 ms 37940 KB Output isn't correct
3 Correct 12 ms 37812 KB Output is correct
4 Correct 12 ms 37980 KB Output is correct
5 Incorrect 13 ms 37980 KB Output isn't correct
6 Incorrect 13 ms 37980 KB Output isn't correct
7 Incorrect 17 ms 38480 KB Output isn't correct
8 Incorrect 22 ms 38492 KB Output isn't correct
9 Incorrect 20 ms 38492 KB Output isn't correct
10 Incorrect 20 ms 38504 KB Output isn't correct
11 Incorrect 17 ms 38492 KB Output isn't correct
12 Incorrect 17 ms 38620 KB Output isn't correct
13 Incorrect 101 ms 41376 KB Output isn't correct
14 Incorrect 98 ms 45120 KB Output isn't correct
15 Correct 139 ms 52240 KB Output is correct
16 Incorrect 275 ms 54048 KB Output isn't correct
17 Incorrect 452 ms 57768 KB Output isn't correct
18 Incorrect 479 ms 59660 KB Output isn't correct
19 Incorrect 513 ms 61484 KB Output isn't correct
20 Incorrect 561 ms 64812 KB Output isn't correct