Submission #74295

#	Time	Username	Problem	Language	Result	Execution time	Memory
74295		funcsr	Teams (IOI15_teams)	C++17	100 / 100	1804 ms	459648 KiB

teams

#include "teams.h"
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;
#define MAX_N (1<<19)
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back

struct SegTree {
  SegTree *left = NULL, *right = NULL;
  int available;
  SegTree(int a) : available(a) {}

  SegTree *add(int p, int l=0, int r=MAX_N) {
    if (r-l == 1) {
      return new SegTree(available+1);
    }
    int mid = (l+r)/2;
    SegTree *new_left = left, *new_right = right;
    if (p < mid) {
      if (!left) left = new SegTree(0);
      new_left = left->add(p, l, mid);
    }
    else {
      if (!right) right = new SegTree(0);
      new_right = right->add(p, mid, r);
    }
    SegTree *ret = new SegTree(available+1);
    ret->left = new_left;
    ret->right = new_right;
    return ret;
  }
};

int used[MAX_N*2-1];
SegTree *last[MAX_N*2-1];
void setLazy(int k, SegTree *v) {
  last[k] = v;
  if (last[k] != NULL) used[k] = last[k]->available;
}
void push(int k) {
  if (last[k] == NULL) return;
  setLazy(k*2+1, last[k]->left);
  setLazy(k*2+2, last[k]->right);
  last[k] = NULL;
}
int N;
SegTree *seg[500001];

int take(SegTree *x, int a, int b, int num, int k=0, int l=0, int r=MAX_N) {
  if (x == NULL) return num;
  if (num == 0) return 0;
  if (b <= l || r <= a) return num;
  if (a <= l && r <= b) {
    int rest = x->available-used[k];
    if (rest == 0) return num;
    if (num >= rest) {
      setLazy(k, x);
      assert(used[k] == x->available);
      return num - rest;
    }
    else {
      if (r-l==1) {
        int e = min(rest, num);
        used[k] += e;
        return num-e;
      }
      // continue
    }
  }
  push(k);
  num = take(x->left, a, b, num, k*2+1, l, (l+r)/2);
  num = take(x->right, a, b, num, k*2+2, (l+r)/2, r);
  used[k] = used[k*2+1]+used[k*2+2];
  return num;
}
void cleanup(int k=0, int l=0, int r=MAX_N) {
  if (used[k] == 0) return;
  used[k] = 0;
  last[k] = NULL;
  if (r-l == 1) return;
  last[k*2+1] = last[k*2+2] = NULL;
  cleanup(k*2+1, l, (l+r)/2);
  cleanup(k*2+2, (l+r)/2, r);
}

vector<int> G[500001];
void init(int NN, int A[], int B[]) {
  N=NN;
  rep(i, N) G[A[i]].pb(B[i]);
  SegTree *head = new SegTree(0);
  rep(l, N+1) {
    for (int r : G[l]) head = head->add(r);
    seg[l] = head;
  }
}

int can(int M, int K[]) {
  long long sum = 0;
  rep(i, M) sum += K[i];
  if (sum > N) return 0;
  //rep(i, MAX_N*2-1) used[i] = 0, last[i] = NULL;
  cleanup();
  sort(K, K+M);

  rep(i, M) if (take(seg[K[i]], K[i], MAX_N, K[i]) > 0) return 0;
  return 1;
}

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