Submission #1282078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282078		iamhereforfun	Teams (IOI15_teams)	C++20	0 / 100	3127 ms	382068 KiB

teams

// Starcraft 2 enjoyer //

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 5e5 + 5;
const int M = 21e4 + 5;
const int LG = 31;
const int C = 26;
const int INF = 1e9 + 5;
const int P = 31;
const int MOD = 1e9 + 7;

struct PersistentSegmentTree
{
    struct Node
    {
        int sum;
        Node *le, *ri;
        int val(Node *cur)
        {
            return cur ? cur->sum : 0;
        }
        Node(int i)
        {
            sum = i;
            le = ri = NULL;
        }
        Node(Node *cur)
        {
            if (!cur)
            {
                sum = 0;
                return;
            }
            sum = cur->sum;
            le = cur->le;
            ri = cur->ri;
        }
        Node(Node *l, Node *r)
        {
            sum = val(l) + val(r);
            le = l;
            ri = r;
        }
    } *root[N];
    int n;
    Node *build(int l, int r)
    {
        if (l == r)
        {
            return new Node(0);
        }
        else
        {
            int m = (l + r) / 2;
            return new Node(build(l, m), build(m + 1, r));
        }
    }
    Node *update(Node *cur, int v, int p, int l, int r)
    {
        if (l == r)
        {
            return new Node(v + cur->sum);
        }
        else
        {
            int m = (l + r) / 2;
            if (p <= m)
            {
                return new Node(update(cur->le, v, p, l, m), cur->ri);
            }
            else
            {
                return new Node(cur->le, update(cur->ri, v, p, m + 1, r));
            }
        }
    }
    int get(Node *cur, int l, int r, int tl, int tr)
    {
        if (tl > tr)
            return 0;
        if (tl <= l && r <= tr)
        {
            return cur->sum;
        }
        else
        {
            int m = (l + r) / 2;
            return get(cur->le, l, m, tl, min(tr, m)) + get(cur->ri, m + 1, r, max(tl, m + 1), tr);
        }
    }
    PersistentSegmentTree(int n) : n(n) { root[0] = build(0, n - 1); };
    void add(int i, int j)
    {
        root[j] = new Node(root[i]);
    }
    void update(int i, int v, int p)
    {
        root[i] = update(root[i], v, p, 0, n - 1);
    }
    int get(int i, int l, int r)
    {
        if (l > r)
            return 0;
        return get(root[i], 0, n - 1, l, r);
    }
} pst(N);

int n, q, a[N], b[N], k[N], last, offset, m;
pair<int, int> rng[N];

void init(int N, int A[], int B[])
{
    n = N;
    for (int x = 1; x <= n; x++)
    {
        a[x] = A[x];
        b[x] = B[x];
        rng[x] = {a[x], b[x]};
    }
    sort(rng + 1, rng + n + 1);
    last = 0;
    for (int x = 1; x <= n; x++)
    {
        auto &[l, r] = rng[x];
        while (last < l)
        {
            pst.add(last, last + 1);
            last++;
        }
        pst.update(last, 1, r);
    }
    for(int x = last; x <= n; x++)
    {
        pst.add(x, x + 1);
    }
}

int can(int M, int K[])
{
    m = M;
    for(int x = 0; x < m; x++)
    {
        k[x] = K[x];
    }
    last = 0;
    offset = 0;
    sort(k, k + m);
    for (int x = 0; x < m; x++)
    {
        if (k[x] > last)
        {
            last = k[x];
            offset = 0;
        }
        int l = last, r = n, ans = -1;
        // cout << k[x] << " " << offset << "v\n";
        // cout << pst.get(k[x], last, n + 1) << "w\n";
        while (l <= r)
        {
            int m = (l + r) / 2;
            if (pst.get(k[x], last, m) + offset < k[x])
            {
                l = m + 1;
            }
            else
            {
                ans = m;
                r = m - 1;
            }
        }
        // cout << offset << " " << ans << "\n";
        if (ans == -1)
        {
            last = -1;
            break;
        }
        else
        {
            int i = k[x] - (pst.get(k[x], last, ans - 1) + offset);
            if (last == ans)
            {
                offset += -i;
            }
            else
            {
                offset = -i;
            }
        }
        last = ans;
    }
    if (last == -1)
        return 0;
    else
        return 1;
}

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