oj.uz

Submission #847923

# Submission time Handle Problem Language Result Execution time Memory
847923 2023-09-10T20:43:45 Z evenvalue Distributing Candies (IOI21_candies) C++17
100 / 100
 310 ms 42324 KB 
#include "candies.h"
#include <algorithm>
#include <vector>

struct SegTree {
  int n;
  std::vector<long long> mini, maxi, sums, vals;

  SegTree(int _n) : n(_n) {
    mini.assign(n * 2, 0);
    maxi.assign(n * 2, 0);
    sums.assign(n * 2, 0);
    vals.assign(n, 0);
  }

  void update(int idx, int l, int r, int x, int val) {
    if (l == x && r == x + 1) {
      mini[idx] = maxi[idx] = sums[idx] = val;
      return;
    }

    int mid = (l + r) / 2;
    int lidx = idx + 1, ridx = idx + (mid - l) * 2;
    if (x < mid) update(lidx, l, mid, x, val);
    else
      update(ridx, mid, r, x, val);
    mini[idx] = std::min(mini[lidx] + sums[ridx], mini[ridx]);
    maxi[idx] = std::max(maxi[lidx] + sums[ridx], maxi[ridx]);
    sums[idx] = sums[lidx] + sums[ridx];
  }

  // Returns (max, min, i)
  std::tuple<int, int, int> query(int idx, int l, int r,
                                  int sufmin, int sufmax, int sufsum, int c) {
    if (l + 1 == r) {
      return std::make_tuple(std::min(1LL * sufmin, sufsum + mini[idx]),
                             std::max(1LL * sufmax, sufsum + maxi[idx]),
                             l);
    }

    int mid = (l + r) / 2;
    int lidx = idx + 1, ridx = idx + (mid - l) * 2;
    long long nsufmin = std::min(1LL * sufmin, sufsum + mini[ridx]),
              nsufmax = std::max(1LL * sufmax, sufsum + maxi[ridx]),
              nsufsum = sufsum + sums[ridx];

    if (nsufmax - nsufmin > c) return query(ridx, mid, r, sufmin, sufmax, sufsum, c);
    return query(lidx, l, mid, nsufmin, nsufmax, nsufsum, c);
  }

  void update(int x, int val) {
    vals[x] = val;
    update(0, 0, n, x, val);
  }

  // Find the smallest suffix such that max - min > c.
  // If no such suffix, the whole range is returned.
  // Returns (min, max, i)
  std::tuple<int, int, int> query(int c) {
    return query(0, 0, n, 0, 0, 0, c);
  }

  inline int at(int x) { return vals[x]; }
};

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(), q = v.size();
  std::vector<std::vector<std::pair<int, int>>> queriesL(n), queriesR(n);
  for (int i = 0; i < q; ++i) {
    queriesL[l[i]].emplace_back(i, v[i]);
    queriesR[r[i]].emplace_back(i, v[i]);
  }

  std::vector<int> s(n);
  SegTree tree(q);
  for (int i = 0; i < n; ++i) {
    for (auto [idx, val] : queriesL[i]) {
      tree.update(idx, -val);
    }

    auto [mini, maxi, idx] = tree.query(c[i]);
    if (maxi - mini <= c[i]) {
      s[i] = -mini;
    } else {
      if (tree.at(idx) < 0) {
        s[i] = c[i] - maxi;
      } else {
        s[i] = -mini;
      }
    }

    for (auto [idx, val] : queriesR[i]) {
      tree.update(idx, 0);
    }
  }

  return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 40532 KB Output is correct
2 Correct 303 ms 39860 KB Output is correct
3 Correct 284 ms 39576 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 151 ms 24764 KB Output is correct
3 Correct 51 ms 14428 KB Output is correct
4 Correct 277 ms 41700 KB Output is correct
5 Correct 303 ms 42096 KB Output is correct
6 Correct 283 ms 42324 KB Output is correct
7 Correct 242 ms 41812 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 94 ms 22192 KB Output is correct
4 Correct 49 ms 13396 KB Output is correct
5 Correct 148 ms 34244 KB Output is correct
6 Correct 155 ms 35452 KB Output is correct
7 Correct 151 ms 35512 KB Output is correct
8 Correct 148 ms 34388 KB Output is correct
9 Correct 149 ms 35644 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 269 ms 40532 KB Output is correct
7 Correct 303 ms 39860 KB Output is correct
8 Correct 284 ms 39576 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 151 ms 24764 KB Output is correct
11 Correct 51 ms 14428 KB Output is correct
12 Correct 277 ms 41700 KB Output is correct
13 Correct 303 ms 42096 KB Output is correct
14 Correct 283 ms 42324 KB Output is correct
15 Correct 242 ms 41812 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 94 ms 22192 KB Output is correct
19 Correct 49 ms 13396 KB Output is correct
20 Correct 148 ms 34244 KB Output is correct
21 Correct 155 ms 35452 KB Output is correct
22 Correct 151 ms 35512 KB Output is correct
23 Correct 148 ms 34388 KB Output is correct
24 Correct 149 ms 35644 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 49 ms 13660 KB Output is correct
27 Correct 134 ms 24148 KB Output is correct
28 Correct 259 ms 40332 KB Output is correct
29 Correct 298 ms 40656 KB Output is correct
30 Correct 310 ms 40788 KB Output is correct
31 Correct 257 ms 41120 KB Output is correct
32 Correct 289 ms 41296 KB Output is correct