oj.uz

Submission #1050686

# Submission time Handle Problem Language Result Execution time Memory
1050686 2024-08-09T12:35:51 Z LucaLucaM Teams (IOI15_teams) C++17
0 / 100
 2771 ms 524288 KB 
#include "teams.h"
#include <vector>
#include <algorithm>
#include <iostream>

const int NMAX = 5e5;

struct Node {
  int cnt;
  Node *l, *r;
  Node() : cnt(0), l(nullptr), r(nullptr) {}
  Node(int x) : cnt(x) {}
  void refresh() {
    cnt = l -> cnt + r -> cnt;
  }
};

Node* build(int tl, int tr) {
  if (tl == tr) {
    return new Node();
  } else {
    int mid = (tl + tr) / 2;
    Node* ret = new Node();
    ret -> l = build(tl, mid);
    ret -> r = build(mid + 1, tr);
    return ret;
  }
}
Node* update(Node* old, int tl, int tr, int p) {
  if (tl == tr) {
    return new Node(1);
  } else {
    int mid = (tl + tr) / 2;
    Node* nw = new Node();
    *nw = *old;
    if (p <= mid) {
      nw -> l = update(old -> l, tl, mid, p);
    } else {
      nw -> r = update(old -> r, mid + 1, tr, p);
    }
    nw -> refresh();
    return nw;
  }
}
int query(const Node *node, int tl, int tr, int ql) {
  if (ql <= tl) {
    return node -> cnt;
  }
  int mid = (tl + tr) / 2;
  int ret = 0;
  if (ql <= mid) {
    ret += query(node -> l, tl, mid, ql);
  }
  ret += query(node -> r, mid + 1, tr, ql);
  return ret;
}
int kth(const Node* node, int tl, int tr, int p, int k) {
  if (node -> cnt < k) {
    return -1;
  }
  if (tl == tr) {
    return tl;
  }
  int mid = (tl + tr) / 2;
  int st = query(node -> l, tl, mid, p);
  if (st >= k) {
    return kth(node -> l, tl, mid, p, k);
  } else {
    return kth(node -> r, mid + 1, tr, p, k - st);
  }
}

Node* version[NMAX + 1];
std::vector<int> where[NMAX + 1];
int first[NMAX + 1]; // first[p] =def= cel mai mic i a.i. r[i] >= p

int n;
void init(int N, int A[], int B[]) {
  n = N;
  std::vector<std::pair<int, int>> v(n);
  for (int i = 1; i <= NMAX; i++) {
    first[i] = -1;
  }
  for (int i = 0; i < n; i++) {
    v[i] = {B[i], A[i]};
  }
  std::sort(v.begin(), v.end());
  for (int i = 0; i < n; i++) {
    auto [r, l] = v[i];
    where[l].push_back(i);
    if (first[r] == -1) {
      first[r] = i;
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    if (first[i] == -1) {
      first[i] = first[i + 1];
    }
  }
  version[0] = build(0, n - 1);
  for (int l = 1; l <= n; l++) {
    version[l] = new Node();
    *version[l] = *version[l - 1];
    for (const auto &index : where[l]) {
      version[l] = update(version[l], 0, n - 1, index);
    }
  }
  // std::cout << "skibidiuhhhh: " << query(version[0], 0, n - 1, 0) << '\n';
}

int can(int m, int K[]) {
  std::sort(K, K + m);
  // std::cout << m << ' ' << K[0] << ' ' << K[1] << '\n';
  int p = 0;
  for (int i = 0; i < m; i++) {
    p = std::max(p, first[K[i]]);
    // std::cout << " before " << p << ' ' << K[i] << '\n';
    if (p == -1) {
      return 0;
    }
    int q = kth(version[K[i]], 0, n - 1, p, K[i]);
    // std::cout << " after " << q << ' ' << K[i] << '\n';
    if (q == -1) {
      return 0;
    }
    p = q + 1;
  }
  return 1;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Runtime error 10 ms 29868 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 84052 KB Output is correct
2 Correct 87 ms 84048 KB Output is correct
3 Runtime error 134 ms 167744 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 84312 KB Output is correct
2 Runtime error 137 ms 168036 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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