Submission #498755

#	Time	Username	Problem	Language	Result	Execution time	Memory
498755		Lam_lai_cuoc_doi	Teams (IOI15_teams)	C++17	0 / 100	4069 ms	324668 KiB

teams

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 5e5 + 5;
constexpr ll Inf = 1e17;
struct node
{
    int cnt;
    node *l, *r;
    node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
} tmp;

node *f[N], *nil;

pair<int, int> s[N];
int n, a[N];
ll dp[N];

void Update(node *st, int l, int r, const int &x, const int &v)
{
    if (l == x && r == x)
    {
        st->cnt += v;
        return;
    }

    if ((l + r) / 2 >= x)
    {
        node *temp = new node;
        *temp = *st->l;
        st->l = temp;

        Update(st->l, l, (l + r) / 2, x, v);
    }
    else
    {
        node *temp = new node;
        *temp = *st->r;
        st->r = temp;

        Update(st->r, (l + r) / 2 + 1, r, x, v);
    }

    st->cnt = st->l->cnt + st->r->cnt;
}

void init(int m, int A[], int B[])
{
    nil = &tmp;
    nil->l = nil->r = nil;

    n = m;
    for (int i = 0; i < m; ++i)
        s[i] = make_pair(A[i], B[i]);
    sort(s, s + n);

    f[0] = new node(nil, nil, 0);

    for (int i = 1, j = 0; i <= n; ++i)
    {
        f[i] = new node;
        *f[i] = *f[i - 1];
        while (j < n && s[i].first <= i)
        {
            Update(f[i], 1, n, s[j].second, 1);
            ++j;
        }
    }
}

int Get(node *st, int l, int r, const int &a, const int &b)
{
    if (l > b || r < a)
        return 0;
    if (l >= a && r <= b)
        return st->cnt;

    return Get(st->l, l, (l + r) / 2, a, b) + Get(st->r, (l + r) / 2 + 1, r, a, b);
}

int can(int m, int k[])
{
    for (int i = 1; i <= m; ++i)
    {
        a[i] = k[i - 1];
        dp[i] = Inf;
    }

    sort(a + 1, a + m + 1);

    for (int i = 1; i <= m; ++i)
    {
        for (int j = i - 1; ~j; --j)
            dp[i] = min(dp[i], dp[j] + Get(f[a[i]], 1, n, a[i], n) - Get(f[a[j] + 1], 1, n, a[i], n));

        if (dp[i] < 0)
            return 0;
    }

    return 1;
}

int q, m, k[N];
int u[N], v[N];
void Read()
{
    cin >> n;

    for (int i = 0; i < n; ++i)
        cin >> u[i] >> v[i];

    init(n, u, v);

    cin >> q;
    while (q--)
    {
        cin >> m;
        for (int i = 0; i < m; ++i)
            cin >> k[i];

        cout << can(m, k) << "\n";
    }
}

void Solve()
{
}

Compilation message (stderr)

teams.cpp: In function 'void read(T&)':
teams.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^
teams.cpp: In constructor 'node::node(node*, node*, int)':
teams.cpp:26:52: warning: declaration of 'cnt' shadows a member of 'node' [-Wshadow]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                                                ~~~~^~~~~~~
teams.cpp:24:9: note: shadowed declaration is here
   24 |     int cnt;
      |         ^~~
teams.cpp:26:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                             ~~~~~~^~~~~~~~~~~
teams.cpp:25:15: note: shadowed declaration is here
   25 |     node *l, *r;
      |               ^
teams.cpp:26:16: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |          ~~~~~~^~~~~~~~~~~
teams.cpp:25:11: note: shadowed declaration is here
   25 |     node *l, *r;
      |           ^
teams.cpp:25:15: warning: 'node::r' will be initialized after [-Wreorder]
   25 |     node *l, *r;
      |               ^
teams.cpp:24:9: warning:   'int node::cnt' [-Wreorder]
   24 |     int cnt;
      |         ^~~
teams.cpp:26:5: warning:   when initialized here [-Wreorder]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |     ^~~~
teams.cpp: In constructor 'node::node(node*, node*, int)':
teams.cpp:26:52: warning: declaration of 'cnt' shadows a member of 'node' [-Wshadow]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                                                ~~~~^~~~~~~
teams.cpp:24:9: note: shadowed declaration is here
   24 |     int cnt;
      |         ^~~
teams.cpp:26:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                             ~~~~~~^~~~~~~~~~~
teams.cpp:25:15: note: shadowed declaration is here
   25 |     node *l, *r;
      |               ^
teams.cpp:26:16: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |          ~~~~~~^~~~~~~~~~~
teams.cpp:25:11: note: shadowed declaration is here
   25 |     node *l, *r;
      |           ^
teams.cpp: In constructor 'node::node(node*, node*, int)':
teams.cpp:26:52: warning: declaration of 'cnt' shadows a member of 'node' [-Wshadow]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                                                ~~~~^~~~~~~
teams.cpp:24:9: note: shadowed declaration is here
   24 |     int cnt;
      |         ^~~
teams.cpp:26:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                             ~~~~~~^~~~~~~~~~~
teams.cpp:25:15: note: shadowed declaration is here
   25 |     node *l, *r;
      |               ^
teams.cpp:26:16: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
   26 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |          ~~~~~~^~~~~~~~~~~
teams.cpp:25:11: note: shadowed declaration is here
   25 |     node *l, *r;
      |           ^
teams.cpp: In function 'int Get(node*, int, int, const int&, const int&)':
teams.cpp:87:44: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   87 | int Get(node *st, int l, int r, const int &a, const int &b)
      |                                 ~~~~~~~~~~~^
teams.cpp:32:8: note: shadowed declaration is here
   32 | int n, a[N];
      |        ^

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