Submission #447093

#	Time	Username	Problem	Language	Result	Execution time	Memory
447093		SuffixAutomata	Distributing Candies (IOI21_candies)	C++17	100 / 100	612 ms	37980 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33