Submission #396767

#	Time	Username	Problem	Language	Result	Execution time	Memory
396767		WLZ	Teams (IOI15_teams)	C++14	77 / 100	4022 ms	521132 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

struct node {
  int l, r, val, idx;
  node *left, *right;
};

node *update(node *cur, int x, int val);

node *propagate(node *cur, int x, int val) {
  if (x <= (cur->l + cur->r) / 2) {
    node *left = cur->left;
    if (left == nullptr) left = new node{cur->l, (cur->l + cur->r) / 2, 0, -1, nullptr, nullptr};
    left = update(left, x, val);
    return new node{cur->l, cur->r, 0, -1, left, cur->right};
  } else {
    node *right = cur->right;
    if (right == nullptr) right = new node{(cur->l + cur->r) / 2 + 1, cur->r, 0, -1, nullptr, nullptr};
    right = update(right, x, val);
    return new node{cur->l, cur->r, 0, -1, cur->left, right};
  }
}

node *update(node *cur, int x, int val) {
  if (cur->l == cur->r) {
    return new node{cur->l, cur->r, cur->val + val, cur->idx, nullptr, nullptr};
  }
  if (cur->idx == x) {
    assert(cur->left == nullptr && cur->right == nullptr);
    return new node{cur->l, cur->r, cur->val + val, cur->idx, nullptr, nullptr};
  } else if (cur->idx != -1) {
    cur = propagate(cur, cur->idx, cur->val);
    cur->idx = -1;
  } else if (cur->val == 0) {
    assert(cur->left == nullptr && cur->right == nullptr);
    return new node{cur->l, cur->r, val, x, nullptr, nullptr};
  }
  cur = propagate(cur, x, val);
  cur->val = (cur->left != nullptr ? cur->left->val : 0) + (cur->right != nullptr ? cur->right->val : 0);
  return cur;
}

int query(node *cur, int l, int r) {
  if (l > r) return 0;
  if (l <= cur->l && cur->r <= r) return cur->val;  
  if (cur->l > r || cur->r < l) return 0;
  if (cur->idx != -1) return (l <= cur->idx && cur->idx <= r ? cur->val : 0);
  int ans = 0;
  if (cur->left != nullptr) ans += query(cur->left, l, r);
  if (cur->right != nullptr) ans += query(cur->right, l, r);
  return ans;
}

int n;
vector<node*> root;

void init(int N, int A[], int B[]) {
  n = N;
  vector< pair<int, int> > v(n);
  for (int i = 0; i < n; i++) v[i].first = A[i], v[i].second = B[i];
  sort(v.begin(), v.end());
  root.resize(n + 1); root[0] = new node{1, n, 0, -1, nullptr, nullptr};
  for (int i = 1, j = 0; i <= n; i++) {
    root[i] = root[i - 1];
    while (j < N && v[j].first == i) root[i] = update(root[i], v[j++].second, +1);
  }
}

int can(int M, int K[]) {
  if (accumulate(K, K + M, 0ll) > n) return 0;
  sort(K, K + M);
  vector<int> used(M, 0);
  for (int i = 0; i < M; i++) {
    int left = K[i], ptr = i;
    while (ptr < M) {
      int cnt = query(root[K[i]], K[ptr], ptr < M - 1 ? K[ptr + 1] - 1 : n) - used[ptr];
      used[ptr] += min(cnt, left);
      left -= min(cnt, left);
      if (left <= 0) break;
      ptr++;
    }
    if (ptr == M && left > 0) return 0;
  }
  return 1;
}

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