Submission #102636

#	Time	Username	Problem	Language	Result	Execution time	Memory
102636		wxh010910	Teams (IOI15_teams)	C++17	100 / 100	2308 ms	348376 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

class node {
 public:
  node* l;
  node* r;
  int s;
};

vector<node*> roots;
node* null;
int n;

void init_null() {
  null = new node();
  null->l = null->r = null;
  null->s = 0;
}

node* insert(node* u, int l, int r, int p) {
  node* v = new node();
  v->l = u->l;
  v->r = u->r;
  v->s = u->s + 1;
  if (l != r) {
    int y = (l + r) >> 1;
    if (p <= y) {
      v->l = insert(v->l, l, y, p);
    } else {
      v->r = insert(v->r, y + 1, r, p);
    }
  }
  return v;
}

int query(node* v, int l, int r, int p) {
  if (l == r) {
    return v->s;
  } else {
    int y = (l + r) >> 1;
    if (p <= y) {
      return query(v->l, l, y, p) + v->r->s;
    } else {
      return query(v->r, y + 1, r, p);
    }
  }
}

int kth(node* v, node* u, int l, int r, int k) {
  if (l == r) {
    return r;
  } else {
    int y = (l + r) >> 1;
    if (k > v->r->s - u->r->s) {
      return kth(v->l, u->l, l, y, k - (v->r->s - u->r->s));
    } else {
      return kth(v->r, u->r, y + 1, r, k);
    }
  }
}

void init(int N, int A[], int B[]) {
  n = N;
  init_null();
  vector<vector<int>> events(n + 1);
  for (int i = 0; i < n; ++i) {
    events[A[i]].push_back(B[i]);
  }
  roots.assign(n + 1, null);
  for (int i = 1; i <= n; ++i) {
    roots[i] = roots[i - 1];
    for (auto j : events[i]) {
      roots[i] = insert(roots[i], 1, n, j);
    }
  }
}

int can(int M, int K[]) {
  sort(K, K + M);
  vector<int> height(1, n);
  vector<int> pos(1, 0);
  vector<int> sum(1, 0);
  for (int i = 0; i < M; ++i) {
    while (height.back() < K[i]) {
      height.pop_back();
      pos.pop_back();
      sum.pop_back();
    }
    int cnt = query(roots[K[i]], 1, n, K[i]) + (sum.back() - query(roots[pos.back()], 1, n, K[i]));
    if (cnt < K[i]) {
      return 0;
    }
    cnt -= K[i];
    while (true) {
      int h = kth(roots[K[i]], roots[pos.back()], 1, n, cnt - sum.back());
      if (h > height.back()) {
        height.pop_back();
        pos.pop_back();
        sum.pop_back();
      } else {
        height.push_back(h);
        pos.push_back(K[i]);
        sum.push_back(cnt);
        break;
      }
    }
  }
  return 1;
}

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