Submission #972577

#	Time	Username	Problem	Language	Result	Execution time	Memory
972577		abczz	Distributing Candies (IOI21_candies)	C++17	100 / 100	377 ms	59080 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{
  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 suffix_mn(ll id, ll l, ll r, ll q) {
    if (r < q) return 1e18;
    ll mid = (l+r)/2;
    if (q <= l) return st[id].sufmn;
    return min(suffix_mn(id*2, l, mid, q)+st[id*2+1].sum, suffix_mn(id*2+1, mid+1, r, q));
  }
  ll suffix_mx(ll id, ll l, ll r, ll q) {
    if (r < q) return -1e18;
    ll mid = (l+r)/2;
    if (q <= l) return st[id].sufmx;
    return max(suffix_mx(id*2, l, mid, q)+st[id*2+1].sum, suffix_mx(id*2+1, mid+1, r, q));
  }
} 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);
    }
    a = ST.solve_mx(1, 0, q-1, c[i], 0);
    b = ST.solve_mn(1, 0, q-1, -c[i], 0);
    if (a == -1) {
      f = ST.suffix_mx(1, 0, q-1, 0);
    }
    else if (a > b) {
      f = c[i] + ST.suffix_mn(1, 0, q-1, a);
    }
    else {
      f = ST.suffix_mx(1, 0, q-1, b);
    }
    F.push_back(f);
  }
  return F;
}

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