Submission #793206

#	Time	Username	Problem	Language	Result	Execution time	Memory
793206		PixelCat	Teams (IOI15_teams)	C++14	100 / 100	3930 ms	278640 KiB

teams

#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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23