Submission #498867

#	Time	Username	Problem	Language	Result	Execution time	Memory
498867		Lam_lai_cuoc_doi	Teams (IOI15_teams)	C++17	77 / 100	850 ms	524292 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;

queue<int> needremove[N];
set<int> remain;
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[j].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 Cal(int x, int y)
{
    return dp[x] + Get(f[a[y]], 1, n, a[y], n) - Get(f[a[x]], 1, n, a[y], n) - a[y];
}

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

    sort(a + 1, a + m + 1);
    remain.clear();
    remain.insert(0);

    for (int i = 1; i <= m; ++i)
    {
        while (!needremove[i].empty())
        {
            int j = needremove[i].front();
            needremove[i].pop();
            auto t = remain.find(j);
            if (t != remain.end())
            {
                remain.erase(t);
                t = remain.lower_bound(j);
                if (t != remain.end() && t != remain.begin())
                {
                    auto r = prev(t);

                    int l = i, mid, h = m;
                    while (l <= h)
                    {
                        mid = (l + h) / 2;
                        if (Cal(*r, mid) >= Cal(*t, mid))
                            l = mid + 1;
                        else
                            h = mid - 1;
                    }

                    if (l <= m)
                        needremove[l].emplace(*t);
                }
            }
        }

        dp[i] = Cal(*remain.rbegin(), i);

        if (dp[i] < 0)
        {
            for (int j = 1; j <= m; ++j)
                while (!needremove[j].empty())
                    needremove[j].pop();
            return 0;
        }

        {
            auto r = --remain.end();
            remain.insert(i);
            auto t = --remain.end();

            int l = i + 1, mid, h = m;
            while (l <= h)
            {
                mid = (l + h) / 2;
                if (Cal(*r, mid) >= Cal(*t, mid))
                    l = mid + 1;
                else
                    h = mid - 1;
            }

            if (l <= m)
                needremove[l].emplace(*t);
        }
    }

    return 1;
}

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:27:52: warning: declaration of 'cnt' shadows a member of 'node' [-Wshadow]
   27 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                                                ~~~~^~~~~~~
teams.cpp:25:9: note: shadowed declaration is here
   25 |     int cnt;
      |         ^~~
teams.cpp:27:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
   27 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                             ~~~~~~^~~~~~~~~~~
teams.cpp:26:15: note: shadowed declaration is here
   26 |     node *l, *r;
      |               ^
teams.cpp:27:16: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
   27 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |          ~~~~~~^~~~~~~~~~~
teams.cpp:26:11: note: shadowed declaration is here
   26 |     node *l, *r;
      |           ^
teams.cpp:26:15: warning: 'node::r' will be initialized after [-Wreorder]
   26 |     node *l, *r;
      |               ^
teams.cpp:25:9: warning:   'int node::cnt' [-Wreorder]
   25 |     int cnt;
      |         ^~~
teams.cpp:27:5: warning:   when initialized here [-Wreorder]
   27 |     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:27:52: warning: declaration of 'cnt' shadows a member of 'node' [-Wshadow]
   27 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                                                ~~~~^~~~~~~
teams.cpp:25:9: note: shadowed declaration is here
   25 |     int cnt;
      |         ^~~
teams.cpp:27:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
   27 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                             ~~~~~~^~~~~~~~~~~
teams.cpp:26:15: note: shadowed declaration is here
   26 |     node *l, *r;
      |               ^
teams.cpp:27:16: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
   27 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |          ~~~~~~^~~~~~~~~~~
teams.cpp:26:11: note: shadowed declaration is here
   26 |     node *l, *r;
      |           ^
teams.cpp: In constructor 'node::node(node*, node*, int)':
teams.cpp:27:52: warning: declaration of 'cnt' shadows a member of 'node' [-Wshadow]
   27 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                                                ~~~~^~~~~~~
teams.cpp:25:9: note: shadowed declaration is here
   25 |     int cnt;
      |         ^~~
teams.cpp:27:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
   27 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                             ~~~~~~^~~~~~~~~~~
teams.cpp:26:15: note: shadowed declaration is here
   26 |     node *l, *r;
      |               ^
teams.cpp:27:16: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
   27 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |          ~~~~~~^~~~~~~~~~~
teams.cpp:26:11: note: shadowed declaration is here
   26 |     node *l, *r;
      |           ^
teams.cpp: In function 'int Get(node*, int, int, const int&, const int&)':
teams.cpp:90:44: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   90 | int Get(node *st, int l, int r, const int &a, const int &b)
      |                                 ~~~~~~~~~~~^
teams.cpp:35:8: note: shadowed declaration is here
   35 | int n, a[N];
      |        ^
teams.cpp: In function 'int Cal(int, int)':
teams.cpp:102:78: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  102 |     return dp[x] + Get(f[a[y]], 1, n, a[y], n) - Get(f[a[x]], 1, n, a[y], n) - a[y];
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

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