제출 #67902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67902		funcsr	팀들 (IOI15_teams)	C++17	77 / 100	4088 ms	388384 KiB

teams

#include "teams.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y)-x.begin())
#define pb push_back
const int MAX_N = 5e5+5;

struct Node {
  int val;
  Node *left, *right;
  Node() : val(0), left(NULL), right(NULL) {}
};
const int MAX_V = MAX_N*30;
Node pool[MAX_V];
int V = 0;
Node* newNode() {
  return &pool[V++];
}

void build(Node *n, int l=0, int r=MAX_N) {
  if (r-l == 1) return;
  n->left = newNode();
  n->right = newNode();
  build(n->left,  l, (l+r)/2);
  build(n->right, (l+r)/2, r);
}
int query(Node *n, int a, int b, int l=0, int r=MAX_N) {
  if (b <= l || r <= a) return 0;
  if (a <= l && r <= b) return n->val;
  return query(n->left, a, b, l, (l+r)/2) + query(n->right, a, b, (l+r)/2, r);
}
Node *add(Node *n, int x, int l=0, int r=MAX_N) {
  if (r-l == 1) {
    Node *ret = newNode();
    ret->val = n->val+1;
    return ret;
  }
  Node *ret = newNode();
  if (x < (l+r)/2) {
    ret->left = add(n->left, x, l, (l+r)/2);
    ret->right = n->right;
  }
  else {
    ret->left = n->left;
    ret->right = add(n->right, x, (l+r)/2, r);
  }
  ret->val = n->val+1;
  return ret;
}

int N;
vector<int> G[MAX_N];
Node *seg[MAX_N];

void init(int NN, int A[], int B[]) {
  N = NN;
  rep(i, N) G[A[i]].pb(B[i]);
  seg[0] = newNode();
  build(seg[0]);
  for (int i=1; i<=N; i++) {
    seg[i] = seg[i-1];
    for (int r : G[i]) seg[i] = add(seg[i], r);
  }
}

int C[MAX_N], demand[MAX_N], used[MAX_N], xs[MAX_N];

int can(int MM, int K[]) {
  long long sum = 0;
  rep(i, MM) sum += K[i];
  if (sum > N) return 0;

  sort(K, K+MM);
  int M = 0;
  rep(i, MM) C[i] = demand[i] = used[i] = 0;
  rep(i, MM) {
    if (M == 0 || xs[M-1] != K[i]) xs[M++] = K[i];
    demand[M-1] += K[i];
  }

  rep(k, M) {
    int d = demand[k];
    for (int r=k; r<M; r++) {
      int rpos = r+1==M?N:(xs[r+1]-1);
      int e = min(query(seg[xs[k]], xs[r], rpos+1)-used[r], d);
      d -= e;
      used[r] += e;
      if (d == 0) break;
    }
    if (d > 0) return 0;
  }
  return 1;
}

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