oj.uz

답안 #1052682

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1052682 2024-08-10T19:14:54 Z thomas_li 팀들 (IOI15_teams) C++17
100 / 100
 342 ms 165204 KB 
#include <bits/stdc++.h>
using namespace std;
namespace std {

template <class Fun> class y_combinator_result {
  Fun fun_;

public:
  template <class T>
  explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

  template <class... Args> decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template <class Fun> decltype(auto) yc(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std
typedef long long ll;
// #define int ll
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int, k>
template <class A, class B> void cmx(A &x, B y) { x = max<A>(x, y); }
template <class A, class B> void cmn(A &x, B y) { x = min<A>(x, y); }
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MM = 5e5 + 5;
struct Node {
  int l, r, sum;
} seg[MM * 30];
int ti = 0;
int build(int l, int r) {
  int u = ti++;
  seg[u].sum = 0;
  if (l != r) {
    int mid = (l + r) / 2;
    seg[u].l = build(l, mid);
    seg[u].r = build(mid + 1, r);
  }
  return u;
};
int inc(int u, int l, int r, int x) {
  int nu = ti++;
  seg[nu] = seg[u];
  if (l == r) {
    seg[nu].sum++;
    return nu;
  }
  int mid = (l + r) / 2;
  if (x <= mid)
    seg[nu].l = inc(seg[nu].l, l, mid, x);
  else if (x > mid)
    seg[nu].r = inc(seg[nu].r, mid + 1, r, x);
  seg[nu].sum = seg[seg[nu].l].sum + seg[seg[nu].r].sum;
  return nu;
};
int sum(int u, int l, int r, int ql, int qr) {
  if (l == ql && r == qr)
    return seg[u].sum;
  int mid = (l + r) / 2;
  if (qr <= mid)
    return sum(seg[u].l, l, mid, ql, qr);
  else if (ql > mid)
    return sum(seg[u].r, mid + 1, r, ql, qr);
  else
    return sum(seg[u].l, l, mid, ql, mid) +
           sum(seg[u].r, mid + 1, r, mid + 1, qr);
};
int n, ver[MM];
void init(int N, int A[], int B[]) {
  n = N;
  vector<vi> ls(n + 1);
  vector<pii> in;
  rep(i, 0, n) {
    int l = A[i], r = B[i];
    ls[r].PB(l);
  }
  int root = build(1, n);
  for (int i = n; i >= 1; i--) {
    for (int l : ls[i]) {
      root = inc(root, 1, n, l);
    }
    ver[i] = root;
  }
}
int cnt[MM];
int can(int M, int K[]) {
  int m = M;
  vi vals;
  rep(i, 0, m) {
    int x = K[i];
    vals.PB(x);
    cnt[x]++;
  }
  if (accumulate(all(vals), 0ll) > n) {
    return 0;
  }
  vals.PB(0);
  sort(all(vals));
  vals.erase(unique(all(vals)), vals.end());
  vi good = {0}, goodv = {0};
  bool done = 0;
  rep(i, 1, sz(vals)) {
    int x = vals[i];
    int tot = cnt[x] * x;
    int cur = 1e9;
    rep(k, 0, sz(good)) {
      int add = sum(ver[x], 1, n, goodv[k] + 1, x) - tot;
      cmn(cur, good[k] + add);
    }
    if (cur < 0) {
      done = 1;
      break;
    }
    while (sz(good) && good.back() >= cur) {
      good.pop_back();
      goodv.pop_back();
    }
    good.PB(cur);
    goodv.PB(vals[i]);
  }
  for (int x : vals)
    cnt[x] = 0;
  return !done;
}

// delta = sumpeople - sumsizes

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 0 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 0 ms 4444 KB Output is correct
17 Correct 0 ms 4444 KB Output is correct
18 Correct 0 ms 4544 KB Output is correct
19 Correct 0 ms 4444 KB Output is correct
20 Correct 0 ms 4444 KB Output is correct
21 Correct 0 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 0 ms 4444 KB Output is correct
25 Correct 0 ms 4444 KB Output is correct
26 Correct 0 ms 4444 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 35156 KB Output is correct
2 Correct 30 ms 34992 KB Output is correct
3 Correct 30 ms 35164 KB Output is correct
4 Correct 35 ms 35408 KB Output is correct
5 Correct 17 ms 33620 KB Output is correct
6 Correct 16 ms 33628 KB Output is correct
7 Correct 16 ms 33800 KB Output is correct
8 Correct 16 ms 33628 KB Output is correct
9 Correct 14 ms 33488 KB Output is correct
10 Correct 13 ms 33236 KB Output is correct
11 Correct 14 ms 33232 KB Output is correct
12 Correct 14 ms 33492 KB Output is correct
13 Correct 20 ms 33776 KB Output is correct
14 Correct 22 ms 34260 KB Output is correct
15 Correct 26 ms 34908 KB Output is correct
16 Correct 30 ms 34896 KB Output is correct
17 Correct 19 ms 33880 KB Output is correct
18 Correct 19 ms 33884 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 35428 KB Output is correct
2 Correct 32 ms 35412 KB Output is correct
3 Correct 59 ms 35232 KB Output is correct
4 Correct 30 ms 35288 KB Output is correct
5 Correct 24 ms 33884 KB Output is correct
6 Correct 24 ms 33872 KB Output is correct
7 Correct 22 ms 33884 KB Output is correct
8 Correct 30 ms 33992 KB Output is correct
9 Correct 14 ms 33492 KB Output is correct
10 Correct 16 ms 33236 KB Output is correct
11 Correct 20 ms 33492 KB Output is correct
12 Correct 35 ms 33480 KB Output is correct
13 Correct 68 ms 33740 KB Output is correct
14 Correct 62 ms 34896 KB Output is correct
15 Correct 41 ms 35160 KB Output is correct
16 Correct 40 ms 35160 KB Output is correct
17 Correct 29 ms 34392 KB Output is correct
18 Correct 30 ms 34008 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 165200 KB Output is correct
2 Correct 226 ms 165204 KB Output is correct
3 Correct 333 ms 165204 KB Output is correct
4 Correct 222 ms 165204 KB Output is correct
5 Correct 104 ms 156488 KB Output is correct
6 Correct 105 ms 156580 KB Output is correct
7 Correct 94 ms 156496 KB Output is correct
8 Correct 104 ms 156500 KB Output is correct
9 Correct 79 ms 155952 KB Output is correct
10 Correct 77 ms 154132 KB Output is correct
11 Correct 82 ms 154648 KB Output is correct
12 Correct 115 ms 155072 KB Output is correct
13 Correct 222 ms 157380 KB Output is correct
14 Correct 342 ms 163636 KB Output is correct
15 Correct 209 ms 163276 KB Output is correct
16 Correct 212 ms 163272 KB Output is correct
17 Correct 126 ms 157880 KB Output is correct
18 Correct 126 ms 157856 KB Output is correct