oj.uz

Submission #436577

# Submission time Handle Problem Language Result Execution time Memory
436577 2021-06-24T16:12:50 Z flashmt Distributing Candies (IOI21_candies) C++17
100 / 100
 964 ms 49312 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 5 ms 716 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 49196 KB Output is correct
2 Correct 941 ms 49212 KB Output is correct
3 Correct 947 ms 49196 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 537 ms 38464 KB Output is correct
3 Correct 132 ms 8116 KB Output is correct
4 Correct 896 ms 49312 KB Output is correct
5 Correct 890 ms 49220 KB Output is correct
6 Correct 816 ms 49212 KB Output is correct
7 Correct 783 ms 49228 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 149 ms 37088 KB Output is correct
4 Correct 109 ms 7980 KB Output is correct
5 Correct 279 ms 44856 KB Output is correct
6 Correct 275 ms 44856 KB Output is correct
7 Correct 309 ms 44956 KB Output is correct
8 Correct 333 ms 44832 KB Output is correct
9 Correct 306 ms 44884 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 861 ms 49196 KB Output is correct
7 Correct 941 ms 49212 KB Output is correct
8 Correct 947 ms 49196 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 537 ms 38464 KB Output is correct
11 Correct 132 ms 8116 KB Output is correct
12 Correct 896 ms 49312 KB Output is correct
13 Correct 890 ms 49220 KB Output is correct
14 Correct 816 ms 49212 KB Output is correct
15 Correct 783 ms 49228 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 149 ms 37088 KB Output is correct
19 Correct 109 ms 7980 KB Output is correct
20 Correct 279 ms 44856 KB Output is correct
21 Correct 275 ms 44856 KB Output is correct
22 Correct 309 ms 44956 KB Output is correct
23 Correct 333 ms 44832 KB Output is correct
24 Correct 306 ms 44884 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 95 ms 8112 KB Output is correct
27 Correct 547 ms 38440 KB Output is correct
28 Correct 951 ms 49220 KB Output is correct
29 Correct 860 ms 49196 KB Output is correct
30 Correct 934 ms 49308 KB Output is correct
31 Correct 915 ms 49284 KB Output is correct
32 Correct 964 ms 49216 KB Output is correct