oj.uz

Submission #396741

# Submission time Handle Problem Language Result Execution time Memory
396741 2021-04-30T17:02:46 Z WLZ Teams (IOI15_teams) C++14
77 / 100
 3749 ms 524292 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

struct node {
  int l, r, val;
  node *left, *right;
};

node *build(int l, int r) {
  if (l == r) return new node{l, r, 0, nullptr, nullptr};
  node *left = build(l, (l + r) / 2), *right = build((l + r) / 2 + 1, r);
  return new node{l, r, 0, left, right};
}

node *update(node *cur, int x, int val) {
  if (cur->l == cur->r) return new node{cur->l, cur->r, cur->val + val, nullptr, nullptr};
  if (x <= cur->left->r) {
    node *left = update(cur->left, x, val);
    return new node{cur->l, cur->r, left->val + cur->right->val, left, cur->right};
  } else {
    node *right = update(cur->right, x, val);
    return new node{cur->l, cur->r, cur->left->val + right->val, cur->left, right}; 
  }
}

int query(node *cur, int l, int r) {
  if (l > r) return 0;
  if (cur->l > r || cur->r < l) return 0;
  if (l <= cur->l && cur->r <= r) return cur->val;
  return query(cur->left, l, r) + query(cur->right, l, r);
}

int n;
vector<node*> root;

void init(int N, int A[], int B[]) {
  n = N;
  vector< pair<int, int> > v(n);
  for (int i = 0; i < n; i++) v[i].first = A[i], v[i].second = B[i];
  sort(v.begin(), v.end());
  root.resize(n + 1); root[0] = build(1, n);
  for (int i = 1, j = 0; i <= n; i++) {
    root[i] = root[i - 1];
    while (j < N && v[j].first == i) root[i] = update(root[i], v[j++].second, +1);
  }
}

int can(int M, int K[]) {
  if (accumulate(K, K + M, 0ll) > n) return 0;
  sort(K, K + M);
  vector<int> used(M, 0);
  for (int i = 0; i < M; i++) {
    int left = K[i], ptr = i;
    while (ptr < M) {
      int cnt = query(root[K[i]], K[ptr], ptr < M - 1 ? K[ptr + 1] - 1 : n) - used[ptr];
      used[ptr] += min(cnt, left);
      left -= min(cnt, left);
      if (left <= 0) break;
      ptr++;
    }
    if (ptr == M && left > 0) return 0;
  }
	return 1;
}

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 96260 KB Output is correct
2 Correct 183 ms 96156 KB Output is correct
3 Correct 178 ms 96192 KB Output is correct
4 Correct 190 ms 96536 KB Output is correct
5 Correct 125 ms 95836 KB Output is correct
6 Correct 107 ms 95828 KB Output is correct
7 Correct 114 ms 95800 KB Output is correct
8 Correct 112 ms 95884 KB Output is correct
9 Correct 2516 ms 92668 KB Output is correct
10 Correct 805 ms 92356 KB Output is correct
11 Correct 117 ms 97144 KB Output is correct
12 Correct 100 ms 92500 KB Output is correct
13 Correct 116 ms 97300 KB Output is correct
14 Correct 114 ms 93908 KB Output is correct
15 Correct 186 ms 96184 KB Output is correct
16 Correct 194 ms 96248 KB Output is correct
17 Correct 130 ms 97456 KB Output is correct
18 Correct 110 ms 97668 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 96440 KB Output is correct
2 Correct 234 ms 96432 KB Output is correct
3 Correct 318 ms 99540 KB Output is correct
4 Correct 182 ms 96540 KB Output is correct
5 Correct 129 ms 96056 KB Output is correct
6 Correct 129 ms 96120 KB Output is correct
7 Correct 127 ms 96016 KB Output is correct
8 Correct 127 ms 96024 KB Output is correct
9 Correct 2404 ms 92716 KB Output is correct
10 Correct 3749 ms 92484 KB Output is correct
11 Correct 1118 ms 97248 KB Output is correct
12 Correct 1435 ms 92740 KB Output is correct
13 Correct 385 ms 97476 KB Output is correct
14 Correct 346 ms 97692 KB Output is correct
15 Correct 203 ms 96316 KB Output is correct
16 Correct 198 ms 96316 KB Output is correct
17 Correct 143 ms 97720 KB Output is correct
18 Correct 143 ms 97752 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1235 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -