oj.uz

Submission #74295

# Submission time Handle Problem Language Result Execution time Memory
74295 2018-08-31T01:22:06 Z funcsr Teams (IOI15_teams) C++17
100 / 100
 1804 ms 459648 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12152 KB Output is correct
2 Correct 11 ms 12156 KB Output is correct
3 Correct 11 ms 12216 KB Output is correct
4 Correct 12 ms 12372 KB Output is correct
5 Correct 11 ms 12372 KB Output is correct
6 Correct 11 ms 12372 KB Output is correct
7 Correct 12 ms 12372 KB Output is correct
8 Correct 14 ms 12420 KB Output is correct
9 Correct 12 ms 12420 KB Output is correct
10 Correct 12 ms 12564 KB Output is correct
11 Correct 11 ms 12564 KB Output is correct
12 Correct 13 ms 12564 KB Output is correct
13 Correct 16 ms 12564 KB Output is correct
14 Correct 12 ms 12564 KB Output is correct
15 Correct 12 ms 12564 KB Output is correct
16 Correct 13 ms 12564 KB Output is correct
17 Correct 12 ms 12564 KB Output is correct
18 Correct 12 ms 12564 KB Output is correct
19 Correct 12 ms 12564 KB Output is correct
20 Correct 12 ms 12564 KB Output is correct
21 Correct 12 ms 12564 KB Output is correct
22 Correct 12 ms 12564 KB Output is correct
23 Correct 12 ms 12564 KB Output is correct
24 Correct 12 ms 12564 KB Output is correct
25 Correct 12 ms 12564 KB Output is correct
26 Correct 13 ms 12564 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 82824 KB Output is correct
2 Correct 194 ms 82824 KB Output is correct
3 Correct 184 ms 82824 KB Output is correct
4 Correct 186 ms 83068 KB Output is correct
5 Correct 126 ms 83068 KB Output is correct
6 Correct 122 ms 83068 KB Output is correct
7 Correct 122 ms 83068 KB Output is correct
8 Correct 120 ms 83068 KB Output is correct
9 Correct 136 ms 83068 KB Output is correct
10 Correct 127 ms 83068 KB Output is correct
11 Correct 122 ms 83068 KB Output is correct
12 Correct 120 ms 83068 KB Output is correct
13 Correct 134 ms 83068 KB Output is correct
14 Correct 144 ms 83692 KB Output is correct
15 Correct 173 ms 87300 KB Output is correct
16 Correct 176 ms 88232 KB Output is correct
17 Correct 133 ms 88232 KB Output is correct
18 Correct 123 ms 88232 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 91324 KB Output is correct
2 Correct 191 ms 91456 KB Output is correct
3 Correct 431 ms 97156 KB Output is correct
4 Correct 194 ms 97156 KB Output is correct
5 Correct 166 ms 97156 KB Output is correct
6 Correct 159 ms 97156 KB Output is correct
7 Correct 127 ms 97156 KB Output is correct
8 Correct 155 ms 97156 KB Output is correct
9 Correct 135 ms 97156 KB Output is correct
10 Correct 150 ms 97156 KB Output is correct
11 Correct 157 ms 97156 KB Output is correct
12 Correct 184 ms 97156 KB Output is correct
13 Correct 293 ms 98100 KB Output is correct
14 Correct 451 ms 107440 KB Output is correct
15 Correct 212 ms 107440 KB Output is correct
16 Correct 220 ms 107440 KB Output is correct
17 Correct 156 ms 107440 KB Output is correct
18 Correct 164 ms 107440 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 392504 KB Output is correct
2 Correct 1070 ms 392504 KB Output is correct
3 Correct 1672 ms 411640 KB Output is correct
4 Correct 1048 ms 411640 KB Output is correct
5 Correct 636 ms 411640 KB Output is correct
6 Correct 631 ms 411640 KB Output is correct
7 Correct 561 ms 411640 KB Output is correct
8 Correct 619 ms 411640 KB Output is correct
9 Correct 653 ms 411640 KB Output is correct
10 Correct 603 ms 411640 KB Output is correct
11 Correct 653 ms 411640 KB Output is correct
12 Correct 726 ms 411640 KB Output is correct
13 Correct 1081 ms 418064 KB Output is correct
14 Correct 1804 ms 459648 KB Output is correct
15 Correct 979 ms 459648 KB Output is correct
16 Correct 941 ms 459648 KB Output is correct
17 Correct 642 ms 459648 KB Output is correct
18 Correct 640 ms 459648 KB Output is correct