Submission #396741

#	Time	Username	Problem	Language	Result	Execution time	Memory
396741		WLZ	Teams (IOI15_teams)	C++14	77 / 100	3749 ms	524292 KiB

teams

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

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

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

int query(node *cur, int l, int r) {
  if (l > r) return 0;
  if (cur->l > r || cur->r < l) return 0;
  if (l <= cur->l && cur->r <= r) return cur->val;
  return query(cur->left, l, r) + query(cur->right, l, r);
}

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] = build(1, n);
  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