Submission #436577

#	Time	Username	Problem	Language	Result	Execution time	Memory
436577		flashmt	Distributing Candies (IOI21_candies)	C++17	100 / 100	964 ms	49312 KiB

candies

#include <bits/stdc++.h>
using namespace std;
const long long oo = 1LL << 60;

struct SegmentTree
{
  int low, mid, high;
  long long save;
  pair<long long, int> minVal, maxVal;
  SegmentTree *l, *r;

  SegmentTree(int low, int high): low(low), high(high)
  {
    mid = (low + high) / 2;
    save = 0;
    minVal = maxVal = {0, low};
    if (low != high)
    {
      l = new SegmentTree(low, mid);
      r = new SegmentTree(mid + 1, high);
    }
  }

  void pushDown()
  {
    if (save)
    {
      l->minVal.first += save;
      l->maxVal.first += save;
      l->save += save;
      r->minVal.first += save;
      r->maxVal.first += save;
      r->save += save;
      save = 0;
    }
  }

  void update(int x, int y, long long value)
  {
    if (low == x && high == y)
    {
      minVal.first += value;
      maxVal.first += value;
      save += value;
    }
    else
    {
      pushDown();
      if (x <= mid)
        l->update(x, min(y, mid), value);
      if (mid < y)
        r->update(max(x, mid + 1), y, value);

      minVal = min(l->minVal, r->minVal);
      maxVal = max(l->maxVal, r->maxVal);
    }
  }

  int find(long long diff, long long curMax, long long curMin)
  {
    if (max(maxVal.first, curMax) - min(minVal.first, curMin) < diff)
      return -1;
    if (low == high)
      return low;
    pushDown();
    if (max(r->maxVal.first, curMax) - min(r->minVal.first, curMin) >= diff)
      return r->find(diff, curMax, curMin);
    return l->find(diff, max(curMax, r->maxVal.first), min(curMin, r->minVal.first));
  }

  pair<long long, int> getMin(int x, int y)
  {
    if (low == x && high == y)
      return minVal;
    pushDown();
    auto u = x <= mid ? l->getMin(x, min(y, mid)) : make_pair(oo, -1);
    auto v = mid < y ? r->getMin(max(x, mid + 1), y) : make_pair(oo, -1);
    return min(u, v);
  }

  pair<long long, int> getMax(int x, int y)
  {
    if (low == x && high == y)
      return maxVal;
    pushDown();
    auto u = x <= mid ? l->getMax(x, min(y, mid)) : make_pair(-oo, -1);
    auto v = mid < y ? r->getMax(max(x, mid + 1), y) : make_pair(-oo, -1);
    return max(u, v);
  }
};


vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
  int n = c.size(), q = l.size();

  vector<vector<int>> queries(n, vector<int>());
  for (int i = 0; i < q; i++)
  {
    queries[l[i]].push_back(i + 1);
    if (r[i] + 1 < n)
      queries[r[i] + 1].push_back(-i - 1);
  }

  SegmentTree *tree = new SegmentTree(0, q);
  vector<int> ans;
  for (int i = 0; i < n; i++)
  {
    for (int id : queries[i])
      if (id < 0) tree->update(-id, q, -v[-id - 1]);
      else tree->update(id, q, v[id - 1]);

    int u = tree->find(c[i], -oo, oo); // reach min or max in [u, q]
    auto [vLast, _] = tree->getMin(q, q);
    auto [vMin, idMin] = tree->getMin(max(u, 0), q);
    if (u < 0) ans.push_back(vLast - vMin);
    else
    {
      auto [vMax, idMax] = tree->getMax(u, q);
      if (idMax > idMin) ans.push_back(c[i] - vMax + vLast);
      else ans.push_back(vLast - vMin);
    }
  }

  return ans;
}

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