oj.uz

Submission #587535

# Submission time Handle Problem Language Result Execution time Memory
587535 2022-07-02T05:03:06 Z wenqi Teams (IOI15_teams) C++17
77 / 100
 4000 ms 366868 KB 
#include "teams.h"
#include <bits/extc++.h>
using namespace std;

struct Node *nodes;
int lol = 0;

struct Node
{
  int l, r;
  Node *lc, *rc;
  int sum;
  Node() {}
  Node(int l, int r) : l(l), r(r), lc(0), rc(0), sum(0) {
    if (l != r)
    {
      int m = (l + r) / 2;
      lc = nodes + lol++;
      rc = nodes + lol++;
      *lc = Node(l, m);
      *rc = Node(m + 1, r);
    }
  }
  Node *update(int p)
  {
    if (p < l or p > r)
      return this;
    Node *n = nodes + lol++;
    n->l = l, n->r = r;
    if (l == r)
    {
      n->sum = sum + 1;
      return n;
    }
    n->lc = lc->update(p);
    n->rc = rc->update(p);
    n->sum = n->lc->sum + n->rc->sum;
    return n;
  }
  int query(int ql, int qr)
  {
    if (qr < l or ql > r)
      return 0;
    if (ql <= l and qr >= r)
      return sum;
    return lc->query(ql, qr) + rc->query(ql, qr);
  }
};

Node *roots[500069];
int N;

void init(int N, int A[], int B[])
{
  ::N = N;
  nodes = new Node[50000069];
  Node *root = new Node(1, N);
  vector<pair<int, int>> ppl;
  for (int i = 0; i < N; i++)
    ppl.push_back({B[i], A[i]});
  sort(ppl.begin(), ppl.end());
  roots[0] = root;
  for (auto [y, x] : ppl)
    roots[y] = root = root->update(x);
  for (int i = 1; i <= N; i++)
    if (not roots[i])
      roots[i] = roots[i - 1];
}

int can(int M, int K[])
{
  vector<int> groups(K, K + M);
  sort(groups.begin(), groups.end());
  vector<tuple<int, int, int, int>> st;
  for (int sz : groups)
  {
    int hate = 0;
    while (not st.empty())
    {
      auto [p, dep, more, s] = st.back();
      if (sz > dep)
      {
        st.pop_back();
        continue;
      }
      if (roots[dep - 1]->query(p + 1, sz) - roots[sz - 1]->query(p + 1, sz) - hate < sz)
      {
        st.pop_back();
        hate += roots[dep]->query(s, p) - roots[sz - 1]->query(s, p) - more;
      }
      else
        break;
    }
    int a = sz;
    int L = st.empty() ? N : get<1>(st.back());
    int b = L + 2;
    int start = st.empty() ? 1 : (get<0>(st.back()) + 1);
    while (b - a > 1)
    {
      int m = (a + b) / 2;
      if (roots[m - 1]->query(start, sz) - roots[sz - 1]->query(start, sz) - hate >= sz)
        b = m;
      else
        a = m;
    }
    if (a == L + 1)
      return 0;
    int G = roots[a]->query(start, sz) - roots[sz - 1]->query(start, sz) - hate - sz;
    st.push_back({sz, a, G, start});
  }
  return 1;
}

Compilation message

teams.cpp: In constructor 'Node::Node(int, int)':
teams.cpp:14:19: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   14 |   Node(int l, int r) : l(l), r(r), lc(0), rc(0), sum(0) {
      |               ~~~~^
teams.cpp:10:10: note: shadowed declaration is here
   10 |   int l, r;
      |          ^
teams.cpp:14:12: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   14 |   Node(int l, int r) : l(l), r(r), lc(0), rc(0), sum(0) {
      |        ~~~~^
teams.cpp:10:7: note: shadowed declaration is here
   10 |   int l, r;
      |       ^
teams.cpp: In constructor 'Node::Node(int, int)':
teams.cpp:14:19: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   14 |   Node(int l, int r) : l(l), r(r), lc(0), rc(0), sum(0) {
      |               ~~~~^
teams.cpp:10:10: note: shadowed declaration is here
   10 |   int l, r;
      |          ^
teams.cpp:14:12: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   14 |   Node(int l, int r) : l(l), r(r), lc(0), rc(0), sum(0) {
      |        ~~~~^
teams.cpp:10:7: note: shadowed declaration is here
   10 |   int l, r;
      |       ^
teams.cpp: In constructor 'Node::Node(int, int)':
teams.cpp:14:19: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   14 |   Node(int l, int r) : l(l), r(r), lc(0), rc(0), sum(0) {
      |               ~~~~^
teams.cpp:10:10: note: shadowed declaration is here
   10 |   int l, r;
      |          ^
teams.cpp:14:12: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   14 |   Node(int l, int r) : l(l), r(r), lc(0), rc(0), sum(0) {
      |        ~~~~^
teams.cpp:10:7: note: shadowed declaration is here
   10 |   int l, r;
      |       ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:53:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   53 | void init(int N, int A[], int B[])
      |           ~~~~^
teams.cpp:51:5: note: shadowed declaration is here
   51 | int N;
      |     ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 312 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 308 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 312 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 65580 KB Output is correct
2 Correct 94 ms 65472 KB Output is correct
3 Correct 89 ms 65496 KB Output is correct
4 Correct 94 ms 65728 KB Output is correct
5 Correct 51 ms 65216 KB Output is correct
6 Correct 47 ms 65156 KB Output is correct
7 Correct 47 ms 65128 KB Output is correct
8 Correct 44 ms 65132 KB Output is correct
9 Correct 133 ms 66236 KB Output is correct
10 Correct 86 ms 65868 KB Output is correct
11 Correct 46 ms 65928 KB Output is correct
12 Correct 42 ms 65984 KB Output is correct
13 Correct 52 ms 65688 KB Output is correct
14 Correct 51 ms 66036 KB Output is correct
15 Correct 77 ms 65444 KB Output is correct
16 Correct 79 ms 65532 KB Output is correct
17 Correct 45 ms 66364 KB Output is correct
18 Correct 46 ms 66384 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 65724 KB Output is correct
2 Correct 96 ms 65736 KB Output is correct
3 Correct 1024 ms 68728 KB Output is correct
4 Correct 88 ms 65728 KB Output is correct
5 Correct 293 ms 65400 KB Output is correct
6 Correct 272 ms 65356 KB Output is correct
7 Correct 50 ms 65392 KB Output is correct
8 Correct 211 ms 65344 KB Output is correct
9 Correct 129 ms 66248 KB Output is correct
10 Correct 302 ms 65972 KB Output is correct
11 Correct 311 ms 66084 KB Output is correct
12 Correct 357 ms 66128 KB Output is correct
13 Correct 517 ms 65960 KB Output is correct
14 Correct 1127 ms 67276 KB Output is correct
15 Correct 298 ms 65592 KB Output is correct
16 Correct 333 ms 65772 KB Output is correct
17 Correct 255 ms 66548 KB Output is correct
18 Correct 268 ms 66484 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 362596 KB Output is correct
2 Correct 710 ms 362560 KB Output is correct
3 Correct 3685 ms 366868 KB Output is correct
4 Correct 635 ms 362664 KB Output is correct
5 Correct 915 ms 359816 KB Output is correct
6 Correct 833 ms 359888 KB Output is correct
7 Correct 259 ms 359896 KB Output is correct
8 Correct 707 ms 359852 KB Output is correct
9 Correct 761 ms 361084 KB Output is correct
10 Correct 849 ms 359336 KB Output is correct
11 Correct 892 ms 359688 KB Output is correct
12 Correct 1051 ms 360108 KB Output is correct
13 Correct 2063 ms 361252 KB Output is correct
14 Execution timed out 4035 ms 363604 KB Time limit exceeded
15 Halted 0 ms 0 KB -