Submission #1242718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242718		BlockOG	Teams (IOI15_teams)	C++20	0 / 100	901 ms	589824 KiB

teams

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

struct SegTree {
    int v = 0;

    int cl, cr;
    SegTree *l = NULL, *r = NULL;

    SegTree(int cl, int cr) : cl(cl), cr(cr) {}

    void add(int i) {
        v++;
        if (cr - cl > 1) {
            int cm = (cl + cr) / 2;

            if (i < cm) {
                if (!l) l = new SegTree(cl, cm);
                l->add(i);
            } else {
                if (!r) r = new SegTree(cm, cr);
                r->add(i);
            }
        }
    }

    int get(int il, int ir) {
        if (il <= cl && cr <= ir) return v;

        int cm = (cl + cr) / 2;
        int res = 0;
        if (l && cl < ir && il < cm) res += l->get(il, ir);
        if (r && cm < ir && il < cr) res += r->get(il, ir);

        return res;
    }
};

struct SegTree2D {
    int cl, cr;
    SegTree2D *l = NULL, *r = NULL;
    SegTree d;

    SegTree2D(int cl, int cr, int dl, int dr) : cl(cl), cr(cr), d(dl, dr) {}

    void add(int x, int y) {
        d.add(y);
        if (cr - cl > 1) {
            int cm = (cl + cr) / 2;

            if (x < cm) {
                if (!l) l = new SegTree2D(cl, cm, d.cl, d.cr);
                l->add(x, y);
            } else {
                if (!r) r = new SegTree2D(cm, cr, d.cl, d.cr);
                r->add(x, y);
            }
        }
    }

    int get(int xl, int xr, int yl, int yr) {
        if (xl <= cl && cr <= xr) return d.get(yl, yr);

        int cm = (cl + cr) / 2;
        int res = 0;
        if (l && cl < xr && xl < cm) res += l->get(xl, xr, yl, yr);
        if (r && cm < xr && xl < cr) res += r->get(xl, xr, yl, yr);

        return res;
    }
};

SegTree2D root(0, 500000, 0, 500000);

void init(int n, int a[], int b[]) {
    fo(i, 0, n) root.add(a[i], b[i]);
}

int can(int m, int k[]) {
    sort(k, k + m);

    vector<pair<int, int>> st = {{-1, 500000}};
    fo(i, 0, m) {
        int j = k[i];

        while (st.back().s < j) st.pob();

        int xr = j, yl = j;
        while (st.size()) {
            auto [xl, yr] = st.back();

            int cres = root.get(xl + 1, xr + 1, yl, yr + 1);
            if (cres <= j) {
                j -= cres;
                yl = yr + 1;
                st.pob();

                if (j <= 0) {
                    st.pb({xr, yr});
                    break;
                }
            } else {
                int l = yl + 1, r = yr;
                while (l < r) {
                    int mid = (l + r + 1) / 2;
                    if (root.get(xl + 1, xr + 1, yl, mid) <= j) l = mid;
                    else r = mid - 1;
                }

                st.pb({xr, r});
                break;
            }
        }

        if (st.empty()) return 0;
    }

    return 1;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23