Submission #587535

#	Time	Username	Problem	Language	Result	Execution time	Memory
587535		wenqi	Teams (IOI15_teams)	C++17	77 / 100	4035 ms	366868 KiB

teams

#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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23