Submission #237931

#	Time	Username	Problem	Language	Result	Execution time	Memory
237931		rama_pang	Teams (IOI15_teams)	C++14	100 / 100	1936 ms	277104 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
 
namespace SegmentTree { // Persistent Segment Tree
  const int LIM = 2e7;
  
  struct Node {
    int value = 0;
    int lc = -1;
    int rc = -1;
  };
  
  vector<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];
    map<int, int> add;
    for (auto j : events[i]) {
      if (active[j]) {
        active[j] = 0;
        add[B[j]]--;
      } else {
        active[j] = 1;
        add[B[j]]++;
      }
    }
    for (auto j : add) {
      segtree[i] = Update(segtree[i], 1, N, j.first, j.second);
    }
  }
}
 
int can(int M, int K[]) {
  sort(K, K + M); ANSWER = 1;
  int old_size = nodes_cnt;
  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);
  }
  nodes_cnt = old_size;
	return ANSWER;
}

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