Submission #237920

#	Time	Username	Problem	Language	Result	Execution time	Memory
237920		rama_pang	Teams (IOI15_teams)	C++14	77 / 100	1522 ms	524292 KiB

teams

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

namespace SegmentTree { // Persistent Segment Tree
  struct Node {
    int value = 0;
    Node *lc = nullptr;
    Node *rc = nullptr;
  };

  Node *Copy(Node *n) {
    Node *res = new Node();
    res->value = n->value;
    res->lc = n->lc;
    res->rc = n->rc;
    return res;
  }

  void Pull(Node *n, Node *lc, Node *rc) {
    n->value = lc->value + rc->value;
  }

  Node *Update(Node *n, int tl, int tr, int p, int v) {
    if (p < tl || tr < p) return n;
    Node *x = Copy(n);
    if (tl == tr) { x->value += v; return x; }
    int mid = (tl + tr) / 2;
    x->lc = Update(x->lc, tl, mid, p, v);
    x->rc = Update(x->rc, mid + 1, tr, p, v);
    Pull(x, x->lc, x->rc);
    return x;
  }

  Node *Build(int tl, int tr) {
    Node *n = new Node();
    if (tl == tr) return n;
    int mid = (tl + tr) / 2;
    n->lc = Build(tl, mid);
    n->rc = Build(mid + 1, tr);
    return n;
  }

  Node *SetZero(Node *n, int tl, int tr, int l, int r) {
    if (r < tl || tr < l || tl > tr || l > r) return n;
    Node *x = Copy(n);
    if (l <= tl && tr <= r) { x->value = 0; return x; }
    int mid = (tl + tr) / 2;
    x->lc = SetZero(x->lc, tl, mid, l, r);
    x->rc = SetZero(x->rc, mid + 1, tr, l, r);
    Pull(x, x->lc, x->rc);
    return x;
  }
}

using namespace SegmentTree;

int N;
int ANSWER;
vector<Node*> segtree; // segtree[i] = set of active interval's B that contain i

Node *Walk(Node *avail, Node *used, int K, int tl, int tr) { // Use K first Bs of (avail - used)
  if (avail->value - used->value < K) ANSWER = 0;
  if (K == 0 || ANSWER == 0) return used;
  Node *x = Copy(used);
  if (tl == tr) { x->value += K; return x; }
  int left_value = avail->lc->value - used->lc->value;
  int mid = (tl + tr) / 2;
  if (K <= left_value) {
    x->lc = Walk(avail->lc, x->lc, K, tl, mid);
  } else {
    x->lc = avail->lc;
    x->rc = Walk(avail->rc, x->rc, K - left_value, mid + 1, tr);
  }
  Pull(x, x->lc, x->rc);
  return x;
}

void init(int N_, int A[], int B[]) {
  N = N_;
  segtree.assign(N + 1,nullptr);
  segtree[0] = Build(1, N);

  vector<vector<int>> events(N + 2);
  for (int i = 0; i < N; i++) {
    events[A[i] + 0].emplace_back(i);
    events[B[i] + 1].emplace_back(i);
  }

  vector<int> active(N, 0);
  for (int i = 1; i <= N; i++) {
    segtree[i] = segtree[i - 1];
    for (auto j : events[i]) {
      if (active[j]) {
        active[j] = 0;
        segtree[i] = Update(segtree[i], 1, N, B[j], -1);
      } else {
        active[j] = 1;
        segtree[i] = Update(segtree[i], 1, N, B[j], +1);
      }
    }
  }
}

int can(int M, int K[]) {
  sort(K, K + M); ANSWER = 1;
  Node *used = segtree[0];
  for (int i = 0; i < M; i++) {
    used = SetZero(used, 1, N, 1, K[i] - 1);
    used = Walk(segtree[K[i]], used, K[i], 1, N);
  }
	return ANSWER;
}

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