oj.uz

Submission #102636

# Submission time Handle Problem Language Result Execution time Memory
102636 2019-03-26T12:29:20 Z wxh010910 Teams (IOI15_teams) C++17
100 / 100
 2308 ms 348376 KB 
#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

class node {
 public:
  node* l;
  node* r;
  int s;
};

vector<node*> roots;
node* null;
int n;

void init_null() {
  null = new node();
  null->l = null->r = null;
  null->s = 0;
}

node* insert(node* u, int l, int r, int p) {
  node* v = new node();
  v->l = u->l;
  v->r = u->r;
  v->s = u->s + 1;
  if (l != r) {
    int y = (l + r) >> 1;
    if (p <= y) {
      v->l = insert(v->l, l, y, p);
    } else {
      v->r = insert(v->r, y + 1, r, p);
    }
  }
  return v;
}

int query(node* v, int l, int r, int p) {
  if (l == r) {
    return v->s;
  } else {
    int y = (l + r) >> 1;
    if (p <= y) {
      return query(v->l, l, y, p) + v->r->s;
    } else {
      return query(v->r, y + 1, r, p);
    }
  }
}

int kth(node* v, node* u, int l, int r, int k) {
  if (l == r) {
    return r;
  } else {
    int y = (l + r) >> 1;
    if (k > v->r->s - u->r->s) {
      return kth(v->l, u->l, l, y, k - (v->r->s - u->r->s));
    } else {
      return kth(v->r, u->r, y + 1, r, k);
    }
  }
}

void init(int N, int A[], int B[]) {
  n = N;
  init_null();
  vector<vector<int>> events(n + 1);
  for (int i = 0; i < n; ++i) {
    events[A[i]].push_back(B[i]);
  }
  roots.assign(n + 1, null);
  for (int i = 1; i <= n; ++i) {
    roots[i] = roots[i - 1];
    for (auto j : events[i]) {
      roots[i] = insert(roots[i], 1, n, j);
    }
  }
}

int can(int M, int K[]) {
  sort(K, K + M);
  vector<int> height(1, n);
  vector<int> pos(1, 0);
  vector<int> sum(1, 0);
  for (int i = 0; i < M; ++i) {
    while (height.back() < K[i]) {
      height.pop_back();
      pos.pop_back();
      sum.pop_back();
    }
    int cnt = query(roots[K[i]], 1, n, K[i]) + (sum.back() - query(roots[pos.back()], 1, n, K[i]));
    if (cnt < K[i]) {
      return 0;
    }
    cnt -= K[i];
    while (true) {
      int h = kth(roots[K[i]], roots[pos.back()], 1, n, cnt - sum.back());
      if (h > height.back()) {
        height.pop_back();
        pos.pop_back();
        sum.pop_back();
      } else {
        height.push_back(h);
        pos.push_back(K[i]);
        sum.push_back(cnt);
        break;
      }
    }
  }
  return 1;
}

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 62544 KB Output is correct
2 Correct 152 ms 62584 KB Output is correct
3 Correct 167 ms 62620 KB Output is correct
4 Correct 166 ms 62840 KB Output is correct
5 Correct 115 ms 60920 KB Output is correct
6 Correct 106 ms 60920 KB Output is correct
7 Correct 107 ms 60940 KB Output is correct
8 Correct 95 ms 60968 KB Output is correct
9 Correct 107 ms 58808 KB Output is correct
10 Correct 102 ms 58356 KB Output is correct
11 Correct 129 ms 61624 KB Output is correct
12 Correct 100 ms 58648 KB Output is correct
13 Correct 121 ms 62040 KB Output is correct
14 Correct 129 ms 60272 KB Output is correct
15 Correct 149 ms 62456 KB Output is correct
16 Correct 172 ms 62376 KB Output is correct
17 Correct 118 ms 62200 KB Output is correct
18 Correct 103 ms 62124 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 62840 KB Output is correct
2 Correct 207 ms 62840 KB Output is correct
3 Correct 450 ms 62968 KB Output is correct
4 Correct 180 ms 62840 KB Output is correct
5 Correct 162 ms 61256 KB Output is correct
6 Correct 144 ms 61176 KB Output is correct
7 Correct 103 ms 61176 KB Output is correct
8 Correct 118 ms 61148 KB Output is correct
9 Correct 102 ms 58792 KB Output is correct
10 Correct 120 ms 58460 KB Output is correct
11 Correct 125 ms 61836 KB Output is correct
12 Correct 141 ms 58736 KB Output is correct
13 Correct 240 ms 62272 KB Output is correct
14 Correct 467 ms 62200 KB Output is correct
15 Correct 204 ms 62628 KB Output is correct
16 Correct 168 ms 62584 KB Output is correct
17 Correct 139 ms 62328 KB Output is correct
18 Correct 130 ms 62340 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1342 ms 348084 KB Output is correct
2 Correct 1283 ms 348376 KB Output is correct
3 Correct 2308 ms 348364 KB Output is correct
4 Correct 1105 ms 348124 KB Output is correct
5 Correct 621 ms 338936 KB Output is correct
6 Correct 610 ms 339136 KB Output is correct
7 Correct 544 ms 339020 KB Output is correct
8 Correct 608 ms 339156 KB Output is correct
9 Correct 601 ms 324060 KB Output is correct
10 Correct 632 ms 337908 KB Output is correct
11 Correct 660 ms 338408 KB Output is correct
12 Correct 727 ms 338924 KB Output is correct
13 Correct 1365 ms 341568 KB Output is correct
14 Correct 1997 ms 344616 KB Output is correct
15 Correct 1061 ms 346576 KB Output is correct
16 Correct 977 ms 346744 KB Output is correct
17 Correct 679 ms 341412 KB Output is correct
18 Correct 641 ms 341388 KB Output is correct