Submission #1280969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280969		windowwife	Teams (IOI15_teams)	C++20	100 / 100	1139 ms	227180 KiB

teams

#ifndef rtgsp
#include "teams.h"
#endif

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 5e5 + 2;
struct Student
{
    int A, B;
    bool operator < (const Student& other) const
    {
        if (B != other.B) return B < other.B;
        return A < other.A;
    }
}s[maxn];
struct Node
{
    int L, R, val;
    Node()
    {
        L = R = val = 0;
    }
};
struct PST
{
    vector<Node> st = {Node()};
    int cnt = 1;
    Node join (int l, int r)
    {
        Node C;
        C.L = l;
        C.R = r;
        C.val = st[l].val + st[r].val;
        return C;
    }
    int upd (int node, int l, int r, int idx, int val)
    {
        if (l == r)
        {
            st.push_back(Node());
            st.back().val = st[node].val + val;
            return cnt++;
        }
        int m = (l + r)/2;
        if (idx <= m) st.push_back(join(upd(st[node].L, l, m, idx, val), st[node].R));
        else st.push_back(join(st[node].L, upd(st[node].R, m + 1, r, idx, val)));
        return cnt++;
    }
    int walk (int node1, int node2, int l, int r, int val)
    {
        if (st[node2].val - st[node1].val < val) return -1;
        if (l == r) return l;
        int m = (l + r)/2, leftnode = st[st[node2].L].val - st[st[node1].L].val;
        if (leftnode < val)
            return walk(st[node1].R, st[node2].R, m + 1, r, val - leftnode);
        return walk(st[node1].L, st[node2].L, l, m, val);
    }
    int get (int node, int l, int r, int cl, int cr)
    {
        if (cl > cr || cr < l || r < cl) return 0;
        if (cl <= l && r <= cr) return st[node].val;
        int m = (l + r)/2;
        return get(st[node].L, l, m, cl, cr) + get(st[node].R, m + 1, r, cl, cr);
    }
}pst;
int n, root[maxn];
vector<int> event[maxn];
void init (int N, int A[], int B[])
{
    n = N;
    for (int i = 1; i <= n; i++)
        s[i] = {A[i - 1], B[i - 1]};
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++)
        event[s[i].A].push_back(i);
    for (int i = 1; i <= n; i++)
    {
        root[i] = root[i - 1];
        for (int j : event[i])
            root[i] = pst.upd(root[i], 1, n, j, 1);
    }
}
int m, k[maxn];
vector<pair<int, int>> corner;
int can (int M, int K[])
{
    m = M;
    int sum = 0;
    for (int i = 1; i <= m; i++)
    {
        k[i] = K[i - 1];
        sum += k[i];
    }
    if (sum > n) return 0;
    sort(k + 1, k + m + 1);
    corner.clear();
    for (int i = 1, j = 1; i <= m; i++)
    {
        if (k[i] > s[n].B) return 0;
        j = i;
        int req = k[i];
        while (j < m && k[i] == k[j + 1])
        {
            req += k[i];
            ++j;
        }
        int l = 1, r = n, m = 0;
        while (l <= r)
        {
            m = (l + r)/2;
            if (s[m].B >= k[i]) r = m - 1;
            else l = m + 1;
        }
        while (!corner.empty() && corner.back().second < l) corner.pop_back();
        int cnt = 0, easy = 0;
        if (corner.empty())
        {
            cnt = pst.get(root[k[i]], 1, n, l, n);
            easy = pst.get(root[k[i]], 1, n, 1, l - 1);
        }
        else
        {
            cnt = pst.get(root[k[i]], 1, n, l, corner.back().second) - pst.get(root[corner.back().first], 1, n, l, corner.back().second);
            easy = pst.get(root[k[i]], 1, n, 1, l - 1) - pst.get(root[corner.back().first], 1, n, 1, l - 1);
        }
        while (cnt < req)
        {
            if (corner.empty())
            {
                return 0;
            }
            l = corner.back().second + 1;
            r = corner.back().first;
            corner.pop_back();
            if (corner.empty())
            {
                cnt += pst.get(root[k[i]], 1, n, l, n);
                easy += pst.get(root[r], 1, n, 1, l - 1);
            }
            else
            {
                cnt += pst.get(root[k[i]], 1, n, l, corner.back().second) - pst.get(root[corner.back().first], 1, n, l, corner.back().second);
                easy += pst.get(root[r], 1, n, 1, l - 1) - pst.get(root[corner.back().first], 1, n, 1, l - 1);
            }
        }
        if (corner.empty()) l = pst.walk(root[0], root[k[i]], 1, n, req + easy);
        else l = pst.walk(root[corner.back().first], root[k[i]], 1, n, req + easy);
        corner.push_back({k[i], l});
        i = j;
    }
    return 1;
}
#ifdef rtgsp
int A[maxn], B[maxn], K[maxn];
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int x, y;
        cin >> x >> y;
        A[i - 1] = x;
        B[i - 1] = y;
    }
    init(N, A, B);
    cin >> Q;
    for (int i = 1; i <= Q; i++)
    {
        int M;
        cin >> M;
        for (int j = 1; j <= M; j++)
        {
            cin >> K[j - 1];
        }
        cout << can(M, K) << '\n';
        for (int j = 1; j <= M; j++)
            K[j - 1] = 0;
    }
}
#endif

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