Submission #237921

#	Time	Username	Problem	Language	Result	Execution time	Memory
237921		rama_pang	Teams (IOI15_teams)	C++14	Compilation error	0 ms	0 KiB

teams

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

namespace SegmentTree { // Persistent Segment Tree
  static const int LIM = 5e7;
  struct Node {
    int value = 0;
    int lc = -1;
    int rc = -1;
  };

  Node d[LIM];
  int nodes_cnt = 0;

  int Copy(int n) {
    d[nodes_cnt] = d[n];
    return nodes_cnt++;
  }

  void Pull(int n, int lc, int rc) {
    d[n].value = d[lc].value + d[rc].value;
  }

  int Update(int n, int tl, int tr, int p, int v) {
    if (p < tl || tr < p) return n;
    int x = Copy(n);
    if (tl == tr) { d[x].value += v; return x; }
    int mid = (tl + tr) / 2;
    d[x].lc = Update(d[x].lc, tl, mid, p, v);
    d[x].rc = Update(d[x].rc, mid + 1, tr, p, v);
    Pull(x, d[x].lc, d[x].rc);
    return x;
  }

  int Build(int tl, int tr) {
    int n = nodes_cnt++;
    if (tl == tr) return n;
    int mid = (tl + tr) / 2;
    d[n].lc = Build(tl, mid);
    d[n].rc = Build(mid + 1, tr);
    return n;
  }

  int Query(int n, int tl, int tr, int p) {
    if (tl == tr) return d[n].value;
    int mid = (tl + tr) / 2;
    if (p <= mid) return Query(d[n].lc, tl, mid, p);
    return Query(d[n].rc, mid + 1, tr, p);
  }

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

using namespace SegmentTree;

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

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

void init(int N_, int A[], int B[]) {
  N = N_;
  segtree.resize(N + 1);
  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;
  int 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;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N;
  cin >> N;
  int A[N] = {}, B[N] = {};
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
  }
  init(N, A, B);
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int M;
    cin >> M;
    int K[M] = {};
    for (int j = 0; j < M; j++) {
      cin >> K[j];
    }
    cout << can(M, K) << "\n";
  }
}

Compilation message (stderr)

Compilation timeout while compiling teams