oj.uz

답안 #447093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
447093 2021-07-24T13:07:59 Z SuffixAutomata 사탕 분배 (IOI21_candies) C++17
100 / 100
 612 ms 37980 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#include "candies.h"

struct info {
  ll mi, mx, laz;
  const info operator+(const info &o) const {
    return {min(mi, o.mi), max(mx, o.mx), 0};
  }
  void tag(ll dt) {
    laz += dt;
    mi += dt;
    mx += dt;
  }
} segt[200005 << 2];

void pd(int idx, int l, int r) {
  if (r - l == 1)
    return;
  segt[idx * 2].tag(segt[idx].laz);
  segt[idx * 2 + 1].tag(segt[idx].laz);
  segt[idx].laz = 0;
}
void ad(int idx, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R)
    return segt[idx].tag(v);
  if (R <= l || r <= L)
    return;
  pd(idx, l, r);
  ad(idx * 2, l, (l + r) / 2, L, R, v);
  ad(idx * 2 + 1, (l + r) / 2, r, L, R, v);
  segt[idx] = segt[idx * 2] + segt[idx * 2 + 1];
}
int fin(int idx, int l, int r, ll sfxmin, ll sfxmax, int cap, ll tot) {
  if (r - l == 1) {
    sfxmin = min(sfxmin, segt[idx].mi);
    sfxmax = max(sfxmax, segt[idx].mx);
    // cout << cap << ' ' << sfxmin << ' ' << sfxmax << ' ' << l << endl;
    if (sfxmin == segt[idx].mi)
      return tot - (sfxmax - cap);
    return tot - sfxmin;
  }
  pd(idx, l, r);
  ll nmin = min(sfxmin, segt[idx * 2 + 1].mi);
  ll nmax = max(sfxmax, segt[idx * 2 + 1].mx);
  if (nmax - nmin >= cap)
    return fin(idx * 2 + 1, (l + r) / 2, r, sfxmin, sfxmax, cap, tot);
  return fin(idx * 2, l, (l + r) / 2, nmin, nmax, cap, tot);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
  int n = c.size();
  int q = l.size();
  vector<vector<pair<int, int>>> op(n + 1);
  std::vector<int> s(n);
  for (int i = 0; i < q; i++) {
    op[l[i]].push_back({i, v[i]});
    op[r[i] + 1].push_back({i, -v[i]});
  }
  ll tot = 0;
  for (int i = 0; i < n; i++) {
    for (auto [u, dt] : op[i]) {
      tot += dt;
      ad(1, 0, q + 1, u + 1, q + 1, dt);
    }
    // cout << segt[1].mx << ' ' << segt[1].mi << endl;
    if (segt[1].mx - segt[1].mi > c[i])
      s[i] = fin(1, 0, q + 1, 1e18, -1e18, c[i], tot);
    else
      s[i] = tot - segt[1].mi;
    assert(0 <= s[i] && s[i] <= c[i]);
  }
  return s;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 535 ms 36244 KB Output is correct
2 Correct 520 ms 35464 KB Output is correct
3 Correct 511 ms 35296 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 391 ms 25028 KB Output is correct
3 Correct 78 ms 9796 KB Output is correct
4 Correct 542 ms 37424 KB Output is correct
5 Correct 531 ms 37592 KB Output is correct
6 Correct 612 ms 37980 KB Output is correct
7 Correct 533 ms 37436 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 188 ms 23264 KB Output is correct
4 Correct 77 ms 8756 KB Output is correct
5 Correct 237 ms 31232 KB Output is correct
6 Correct 252 ms 31888 KB Output is correct
7 Correct 278 ms 32492 KB Output is correct
8 Correct 274 ms 31036 KB Output is correct
9 Correct 253 ms 32580 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 535 ms 36244 KB Output is correct
7 Correct 520 ms 35464 KB Output is correct
8 Correct 511 ms 35296 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 391 ms 25028 KB Output is correct
11 Correct 78 ms 9796 KB Output is correct
12 Correct 542 ms 37424 KB Output is correct
13 Correct 531 ms 37592 KB Output is correct
14 Correct 612 ms 37980 KB Output is correct
15 Correct 533 ms 37436 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 188 ms 23264 KB Output is correct
19 Correct 77 ms 8756 KB Output is correct
20 Correct 237 ms 31232 KB Output is correct
21 Correct 252 ms 31888 KB Output is correct
22 Correct 278 ms 32492 KB Output is correct
23 Correct 274 ms 31036 KB Output is correct
24 Correct 253 ms 32580 KB Output is correct
25 Correct 1 ms 300 KB Output is correct
26 Correct 98 ms 8752 KB Output is correct
27 Correct 364 ms 24400 KB Output is correct
28 Correct 580 ms 35968 KB Output is correct
29 Correct 569 ms 36444 KB Output is correct
30 Correct 596 ms 36564 KB Output is correct
31 Correct 575 ms 36724 KB Output is correct
32 Correct 597 ms 36904 KB Output is correct