Submission #972526

#	Time	Username	Problem	Language	Result	Execution time	Memory
972526		abczz	Distributing Candies (IOI21_candies)	C++17	8 / 100	345 ms	103864 KiB

candies

#include "candies.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long

using namespace std;

ll n, q;
vector <array<ll, 2>> Q[200000];
struct SegTree{
  ll ans = -1;
  struct Node{
    ll mx = 0;
    ll mn = 0;
    ll sum = 0;
    ll prefmx = 0;
    ll prefmn = 0;
    ll sufmx = 0;
    ll sufmn = 0;
  };
  Node st[800000];
  void merge(ll id) {
    st[id].mx = max(max(st[id*2].mx, st[id*2+1].mx), st[id*2].sufmx + st[id*2+1].prefmx);
    st[id].mn = min(min(st[id*2].mn, st[id*2+1].mn), st[id*2].sufmn + st[id*2+1].prefmn);
    st[id].sum = st[id*2].sum + st[id*2+1].sum;
    st[id].prefmx = max(st[id*2].prefmx, st[id*2].sum+st[id*2+1].prefmx);
    st[id].prefmn = min(st[id*2].prefmn, st[id*2].sum+st[id*2+1].prefmn);
    st[id].sufmx = max(st[id*2+1].sufmx, st[id*2].sufmx + st[id*2+1].sum);
    st[id].sufmn = min(st[id*2+1].sufmn, st[id*2].sufmn + st[id*2+1].sum);
  }
  void update(ll id, ll l, ll r, ll q, ll w) {
    if (l == r) {
      st[id] = {max(0LL, w), min(0LL, w), w, max(0LL, w), min(0LL, w), max(0LL, w), min(0LL, w)};
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, w);
    else update(id*2+1, mid+1, r, q, w);
    merge(id);
  }
  ll query_sum(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql || ql > qr) return 0;
    else if (ql <= l && r <= qr) return st[id].sum;
    ll mid = (l+r)/2;
    return query_sum(id*2, l, mid, ql, qr) + query_sum(id*2+1, mid+1, r, ql, qr);
  }
  ll solve_mx(ll id, ll l, ll r, ll w, ll rmx) {
    if (max(st[id].mx, st[id].sufmx + rmx) <= w) return -1;
    else if (l == r) return l;
    ll mid = (l+r)/2;
    if (st[id*2+1].mx > w || st[id*2+1].sufmx + rmx > w) return solve_mx(id*2+1, mid+1, r, w, rmx);
    else return solve_mx(id*2, l, mid, w, max(rmx + st[id*2+1].sum, st[id*2+1].prefmx));
  }
  ll solve_mn(ll id, ll l, ll r, ll w, ll rmn) {
    if (min(st[id].mn, st[id].sufmn + rmn) >= w) return -1;
    else if (l == r) return l;
    ll mid = (l+r)/2;
    if (st[id*2+1].mn < w || st[id*2+1].sufmn + rmn < w) return solve_mn(id*2+1, mid+1, r, w, rmn);
    else return solve_mn(id*2, l, mid, w, min(rmn + st[id*2+1].sum, st[id*2+1].prefmn));
  }
  ll bound_mx(ll id, ll l, ll r, ll q, ll w) {
    if (r < q) return 0;
    ll mid = (l+r)/2;
    if (q <= l) {
      //cout << l << " " << r << " " << st[id].sum << " " << w << " " << st[id*2].sum << " " << st[id*2+1].prefmx << endl;
      if (st[id].sum > w) ans = max(ans, r);
      else if (l != r && st[id*2+1].prefmx > max(0LL, w-st[id*2].sum)) bound_mx(id*2+1, mid+1, r, q, max(0LL, w-st[id*2].sum));
      else if (l != r && st[id*2].prefmx > w) bound_mx(id*2, l, mid, q, w);
      return st[id].sum;
    }
    ll z = bound_mx(id*2, l, mid, q, w);
    z += bound_mx(id*2+1, mid+1, r, q, w-z);
    return z;
  }
  ll bound_mn(ll id, ll l, ll r, ll q, ll w) {
    if (r < q) return 0;
    ll mid = (l+r)/2;
    if (q <= l) {
      if (st[id].sum < w) ans = max(ans, r);
      else if (st[id*2+1].prefmn < min(0LL, w-st[id*2].sum)) bound_mn(id*2+1, mid+1, r, q, min(0LL, w-st[id*2].sum));
      else if (st[id*2].prefmn < w) bound_mn(id*2, l, mid, q, w);
      return st[id].sum;
    }
    ll z = bound_mn(id*2, l, mid, q, w);
    z += bound_mn(id*2+1, mid+1, r, q, w-z);
    return z;
  }
} ST;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
  ll n = c.size(), q = l.size(), a, b, f;
  vector <int> F;
  for (int i=0; i<q; ++i) {
    Q[l[i]].push_back({i, v[i]});
    if (r[i] != n-1) Q[r[i]+1].push_back({i, 0});
  }
  for (int i=0; i<n; ++i) {
    for (auto [u, w] : Q[i]) {
      ST.update(1, 0, q-1, u, w);
    }
    ST.ans = -1;
    a = ST.solve_mx(1, 0, q-1, c[i], 0);
    b = ST.solve_mn(1, 0, q-1, -c[i], 0);
    //cout << a << " " << b << " " << ST.st[1].mx << endl;
    if (a == -1) {
      a = ST.bound_mn(1, 0, q-1, 0, 0);
      if (ST.ans == -1) f = ST.query_sum(1, 0, q-1, 0, q-1);
      else f = ST.query_sum(1, 0, q-1, ST.ans+1, q-1);
    }
    else if (a > b) {
      ST.bound_mx(1, 0, q-1, a, c[i]);
      f = c[i] + ST.query_sum(1, 0, q-1, ST.ans+1, q-1);
    }
    else {
      ST.bound_mn(1, 0, q-1, b, -c[i]);
      f = ST.query_sum(1, 0, q-1, ST.ans+1, q-1);
    }
    F.push_back(f);
  }
  return F;
}

• Subtask 1: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33