oj.uz

Submission #498868

# Submission time Handle Problem Language Result Execution time Memory
498868 2021-12-26T13:41:43 Z Lam_lai_cuoc_doi Teams (IOI15_teams) C++17
100 / 100
 1785 ms 466956 KB 
#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 int M = 2e5 + 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[M];
set<int> remain;
int n, a[M], id[N];
ll dp[M];

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)
        id[i] = i;

    sort(id, id + m, [&](const int &x, const int &y)
         { return A[x] < A[y] || (A[x] == A[y] && B[x] < B[y]); });

    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 && A[id[j]] <= i)
        {
            Update(f[i], 1, n, B[id[j]], 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

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:28:52: warning: declaration of 'cnt' shadows a member of 'node' [-Wshadow]
   28 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                                                ~~~~^~~~~~~
teams.cpp:26:9: note: shadowed declaration is here
   26 |     int cnt;
      |         ^~~
teams.cpp:28:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
   28 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                             ~~~~~~^~~~~~~~~~~
teams.cpp:27:15: note: shadowed declaration is here
   27 |     node *l, *r;
      |               ^
teams.cpp:28:16: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
   28 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |          ~~~~~~^~~~~~~~~~~
teams.cpp:27:11: note: shadowed declaration is here
   27 |     node *l, *r;
      |           ^
teams.cpp:27:15: warning: 'node::r' will be initialized after [-Wreorder]
   27 |     node *l, *r;
      |               ^
teams.cpp:26:9: warning:   'int node::cnt' [-Wreorder]
   26 |     int cnt;
      |         ^~~
teams.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     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:28:52: warning: declaration of 'cnt' shadows a member of 'node' [-Wshadow]
   28 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                                                ~~~~^~~~~~~
teams.cpp:26:9: note: shadowed declaration is here
   26 |     int cnt;
      |         ^~~
teams.cpp:28:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
   28 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                             ~~~~~~^~~~~~~~~~~
teams.cpp:27:15: note: shadowed declaration is here
   27 |     node *l, *r;
      |               ^
teams.cpp:28:16: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
   28 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |          ~~~~~~^~~~~~~~~~~
teams.cpp:27:11: note: shadowed declaration is here
   27 |     node *l, *r;
      |           ^
teams.cpp: In constructor 'node::node(node*, node*, int)':
teams.cpp:28:52: warning: declaration of 'cnt' shadows a member of 'node' [-Wshadow]
   28 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                                                ~~~~^~~~~~~
teams.cpp:26:9: note: shadowed declaration is here
   26 |     int cnt;
      |         ^~~
teams.cpp:28:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
   28 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |                             ~~~~~~^~~~~~~~~~~
teams.cpp:27:15: note: shadowed declaration is here
   27 |     node *l, *r;
      |               ^
teams.cpp:28:16: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
   28 |     node(node *l = nullptr, node *r = nullptr, int cnt = 0) : l(l), r(r), cnt(cnt) {}
      |          ~~~~~~^~~~~~~~~~~
teams.cpp:27:11: note: shadowed declaration is here
   27 |     node *l, *r;
      |           ^
teams.cpp: In function 'int Get(node*, int, int, const int&, const int&)':
teams.cpp:92:44: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   92 | 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[M], id[N];
      |        ^
teams.cpp: In function 'int Cal(int, int)':
teams.cpp:104:78: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |     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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 134940 KB Output is correct
2 Correct 83 ms 134852 KB Output is correct
3 Correct 89 ms 134980 KB Output is correct
4 Correct 86 ms 135136 KB Output is correct
5 Correct 101 ms 134880 KB Output is correct
6 Correct 83 ms 134936 KB Output is correct
7 Correct 85 ms 134980 KB Output is correct
8 Correct 94 ms 135096 KB Output is correct
9 Correct 83 ms 134884 KB Output is correct
10 Correct 95 ms 134928 KB Output is correct
11 Correct 78 ms 134920 KB Output is correct
12 Correct 89 ms 134880 KB Output is correct
13 Correct 87 ms 134956 KB Output is correct
14 Correct 83 ms 134980 KB Output is correct
15 Correct 84 ms 134864 KB Output is correct
16 Correct 91 ms 134968 KB Output is correct
17 Correct 80 ms 135020 KB Output is correct
18 Correct 86 ms 134988 KB Output is correct
19 Correct 100 ms 134836 KB Output is correct
20 Correct 84 ms 134844 KB Output is correct
21 Correct 84 ms 134956 KB Output is correct
22 Correct 91 ms 134960 KB Output is correct
23 Correct 86 ms 134912 KB Output is correct
24 Correct 86 ms 134868 KB Output is correct
25 Correct 83 ms 134892 KB Output is correct
26 Correct 86 ms 134876 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 192288 KB Output is correct
2 Correct 199 ms 192284 KB Output is correct
3 Correct 206 ms 192268 KB Output is correct
4 Correct 198 ms 193084 KB Output is correct
5 Correct 169 ms 192388 KB Output is correct
6 Correct 157 ms 192276 KB Output is correct
7 Correct 154 ms 192192 KB Output is correct
8 Correct 161 ms 192300 KB Output is correct
9 Correct 359 ms 192356 KB Output is correct
10 Correct 257 ms 191188 KB Output is correct
11 Correct 158 ms 193348 KB Output is correct
12 Correct 167 ms 190276 KB Output is correct
13 Correct 178 ms 193080 KB Output is correct
14 Correct 173 ms 190788 KB Output is correct
15 Correct 195 ms 192176 KB Output is correct
16 Correct 219 ms 192252 KB Output is correct
17 Correct 167 ms 193096 KB Output is correct
18 Correct 166 ms 193092 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 192696 KB Output is correct
2 Correct 208 ms 192680 KB Output is correct
3 Correct 286 ms 195544 KB Output is correct
4 Correct 231 ms 193060 KB Output is correct
5 Correct 506 ms 192732 KB Output is correct
6 Correct 471 ms 192664 KB Output is correct
7 Correct 182 ms 192632 KB Output is correct
8 Correct 391 ms 193092 KB Output is correct
9 Correct 370 ms 192232 KB Output is correct
10 Correct 807 ms 191604 KB Output is correct
11 Correct 568 ms 193832 KB Output is correct
12 Correct 481 ms 190436 KB Output is correct
13 Correct 543 ms 193588 KB Output is correct
14 Correct 327 ms 193980 KB Output is correct
15 Correct 387 ms 192752 KB Output is correct
16 Correct 341 ms 192756 KB Output is correct
17 Correct 431 ms 193592 KB Output is correct
18 Correct 410 ms 193604 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 457924 KB Output is correct
2 Correct 950 ms 458032 KB Output is correct
3 Correct 1294 ms 463740 KB Output is correct
4 Correct 924 ms 458644 KB Output is correct
5 Correct 1537 ms 458500 KB Output is correct
6 Correct 1370 ms 462632 KB Output is correct
7 Correct 588 ms 462548 KB Output is correct
8 Correct 1216 ms 462708 KB Output is correct
9 Correct 1750 ms 457452 KB Output is correct
10 Correct 1785 ms 462824 KB Output is correct
11 Correct 1481 ms 462456 KB Output is correct
12 Correct 1331 ms 463260 KB Output is correct
13 Correct 1642 ms 464928 KB Output is correct
14 Correct 1237 ms 466956 KB Output is correct
15 Correct 1292 ms 465432 KB Output is correct
16 Correct 1180 ms 465504 KB Output is correct
17 Correct 1195 ms 465200 KB Output is correct
18 Correct 1180 ms 465356 KB Output is correct