oj.uz

Submission #793206

# Submission time Handle Problem Language Result Execution time Memory
793206 2023-07-25T15:47:31 Z PixelCat Teams (IOI15_teams) C++14
100 / 100
 3930 ms 278640 KB 
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "teams.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 500'000;
const int MAXND = 10'000'000;

namespace SegTree {
    struct Node {
        Node *l, *r;
        int sum;
        Node(): l(nullptr), r(nullptr), sum(0) {}
    } _nodes[MAXND + 10];
    int _node_count = 0;

    Node* new_node(Node* nd) {
        _node_count++;
        if(nd) _nodes[_node_count] = (*nd);
        else   _nodes[_node_count] = Node();
        return (_nodes + _node_count);
    }

    Node* add(Node* rt, int l, int r, int i, int x) {
        Node* nd = new_node(rt);
        nd->sum += x;
        if(l == r) return nd;
        int m = (l + r) / 2;
        if(i <= m) nd->l = add(nd->l, l, m, i, x);
        else       nd->r = add(nd->r, m + 1, r, i, x);
        return nd;
    }
    int get_sum(Node* rt, int l, int r, int L, int R) {
        if(!rt) return 0;
        if(l >= L && r <= R) return rt->sum;
        int m = (l + r) / 2;
        int res = 0;
        if(L <= m) res += get_sum(rt->l, l, m, L, R);
        if(R > m)  res += get_sum(rt->r, m + 1, r, L, R);
        return res;
    }
}

int n;
vector<int> v[MAXN + 10];
SegTree::Node* seg[MAXN + 10];

// int sum(int u, int d, int l, int r) {
//     d--; l--;
//     return ps[r][u] + ps[l][d] - ps[l][u] - ps[r][d];
// }
int sum(int u, int d, int l, int r) {
    return SegTree::get_sum(seg[r], 1, n, d, u) - SegTree::get_sum(seg[l - 1], 1, n, d, u);
}

pii find_pos(int u, int d, int l, int r, int &rem){
    int hi = u, lo = d - 1;
    while(hi - lo > 1) {
        int mi = (hi + lo) / 2;
        if(sum(mi, d, l, r) <= rem) lo = mi;
        else hi = mi;
    }
    rem -= sum(lo, d, l, r);
    int y = hi;
    hi = r, lo = l - 1;
    while(hi - lo > 1) {
        int mi = (hi + lo) / 2;
        if(sum(y, y, l, mi) <= rem) lo = mi;
        else hi = mi;
    }
    rem -= sum(y, y, l, lo);
    int x = hi;
    return pii(x, y);
}

void init(int N, int A[], int B[]) {
    n = N;
    For(i, 1, n) {
        v[A[i - 1]].eb(B[i - 1]);
    }
    seg[0] = nullptr;
    For(i, 1, n) {
        seg[i] = seg[i - 1];
        for(auto &x:v[i]) seg[i] = SegTree::add(seg[i], 1, n, x, 1);
    }
    // Forr(y, n, 1) For(x, 1, n) cerr << sum(y, y, x, x) << " \n"[x == n];
}

struct Ayaya {
    int l, u, d, minus;
};

int can(int M, int K[]) {
    sort(K, K + M);
    vector<Ayaya> stk;
    stk.eb((Ayaya){ 1, n, 1, 0 });

    // auto out = [&]() {
    //     for(auto &i:stk) {
    //         cerr << i.l << " " << i.u << "~" << i.d << " (-" << i.minus << ")\n";
    //     }
    // };

    bool fail = false;
    For(iter, 0, M - 1) {
        int x = K[iter];
        while(sz(stk) && (stk.back().u < x || stk.back().l > x)) stk.pop_back();
        if(stk.empty()) {
            fail = true;
            goto END;
        }
        if(stk.back().d < x) stk.back().d = x;
        // out();

        int rem = x;
        while(rem > 0) {
            if(stk.empty()) {
                fail = true;
                goto END;
            }
            Ayaya aya = stk.back();
            stk.pop_back();

            int su = sum(aya.u, aya.d, aya.l, x) - aya.minus;
            if(su <= rem) {
                // cerr << su << " " << rem << "  take all\n";
                rem -= su;
                continue;
            }

            rem += aya.minus;
            pii pos = find_pos(aya.u, aya.d, aya.l, x, rem);
            if(pos.S < aya.u) stk.eb((Ayaya){ aya.l, aya.u, pos.S + 1, 0 });
            stk.eb((Ayaya){ pos.F, pos.S, pos.S, rem });
            rem = 0;
        }

        if(stk.empty()) stk.eb((Ayaya){ x + 1, n, 1, 0 });
        else if(stk.back().d > 1) stk.eb((Ayaya){ x + 1, stk.back().d - 1, 1, 0 });
    }
END:
    // cerr << "--- end of test ---\n";
    if(fail) return 0;
    return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 246860 KB Output is correct
2 Correct 81 ms 246748 KB Output is correct
3 Correct 96 ms 246772 KB Output is correct
4 Correct 83 ms 246772 KB Output is correct
5 Correct 82 ms 246752 KB Output is correct
6 Correct 85 ms 246868 KB Output is correct
7 Correct 82 ms 246860 KB Output is correct
8 Correct 82 ms 246860 KB Output is correct
9 Correct 83 ms 246860 KB Output is correct
10 Correct 82 ms 246876 KB Output is correct
11 Correct 83 ms 246768 KB Output is correct
12 Correct 87 ms 246972 KB Output is correct
13 Correct 83 ms 246872 KB Output is correct
14 Correct 84 ms 246868 KB Output is correct
15 Correct 84 ms 246860 KB Output is correct
16 Correct 82 ms 246800 KB Output is correct
17 Correct 84 ms 246800 KB Output is correct
18 Correct 85 ms 246860 KB Output is correct
19 Correct 83 ms 246796 KB Output is correct
20 Correct 82 ms 246784 KB Output is correct
21 Correct 83 ms 246816 KB Output is correct
22 Correct 83 ms 246844 KB Output is correct
23 Correct 87 ms 246820 KB Output is correct
24 Correct 88 ms 246784 KB Output is correct
25 Correct 83 ms 246780 KB Output is correct
26 Correct 86 ms 246872 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 250204 KB Output is correct
2 Correct 114 ms 250632 KB Output is correct
3 Correct 120 ms 250668 KB Output is correct
4 Correct 118 ms 250992 KB Output is correct
5 Correct 96 ms 249496 KB Output is correct
6 Correct 96 ms 249508 KB Output is correct
7 Correct 97 ms 249524 KB Output is correct
8 Correct 98 ms 249488 KB Output is correct
9 Correct 100 ms 249284 KB Output is correct
10 Correct 101 ms 249276 KB Output is correct
11 Correct 96 ms 249324 KB Output is correct
12 Correct 97 ms 249248 KB Output is correct
13 Correct 118 ms 249508 KB Output is correct
14 Correct 106 ms 249668 KB Output is correct
15 Correct 116 ms 250244 KB Output is correct
16 Correct 113 ms 250316 KB Output is correct
17 Correct 100 ms 249372 KB Output is correct
18 Correct 114 ms 249260 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 250704 KB Output is correct
2 Correct 124 ms 250824 KB Output is correct
3 Correct 732 ms 254244 KB Output is correct
4 Correct 120 ms 251944 KB Output is correct
5 Correct 121 ms 250740 KB Output is correct
6 Correct 114 ms 250548 KB Output is correct
7 Correct 103 ms 250652 KB Output is correct
8 Correct 112 ms 250604 KB Output is correct
9 Correct 100 ms 249720 KB Output is correct
10 Correct 124 ms 249844 KB Output is correct
11 Correct 146 ms 250088 KB Output is correct
12 Correct 193 ms 250292 KB Output is correct
13 Correct 459 ms 251080 KB Output is correct
14 Correct 1067 ms 253632 KB Output is correct
15 Correct 248 ms 252068 KB Output is correct
16 Correct 288 ms 252048 KB Output is correct
17 Correct 200 ms 250832 KB Output is correct
18 Correct 203 ms 250836 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 264732 KB Output is correct
2 Correct 396 ms 264836 KB Output is correct
3 Correct 2889 ms 278640 KB Output is correct
4 Correct 398 ms 271484 KB Output is correct
5 Correct 195 ms 263208 KB Output is correct
6 Correct 191 ms 263172 KB Output is correct
7 Correct 173 ms 263184 KB Output is correct
8 Correct 186 ms 263072 KB Output is correct
9 Correct 171 ms 262060 KB Output is correct
10 Correct 237 ms 260440 KB Output is correct
11 Correct 292 ms 261028 KB Output is correct
12 Correct 438 ms 262048 KB Output is correct
13 Correct 1762 ms 265424 KB Output is correct
14 Correct 3930 ms 274004 KB Output is correct
15 Correct 606 ms 270140 KB Output is correct
16 Correct 581 ms 270172 KB Output is correct
17 Correct 419 ms 264416 KB Output is correct
18 Correct 390 ms 264520 KB Output is correct