oj.uz

Submission #743085

# Submission time Handle Problem Language Result Execution time Memory
743085 2023-05-17T07:47:14 Z Mauve Distributing Candies (IOI21_candies) C++17
100 / 100
 1106 ms 32188 KB 
// O((n + q) sqrt(q))

#include "candies.h"

#include <algorithm>
#include <cmath>
#include <vector>

struct Buckets {
  int n;
  int bucket_size, bucket_cnt;
  std::vector<int> vals;
  std::vector<long long> mini, maxi, sums;
  Buckets(int _n): n(_n) {
    bucket_size = sqrt(n);
    bucket_cnt = (n + bucket_size - 1) / bucket_size;
    vals.assign(n, 0);
    mini.assign(bucket_cnt, 0);
    maxi.assign(bucket_cnt, 0);
    sums.assign(bucket_cnt, 0);
  }

  void update(int x, int val) {
    vals[x] = val;
    int bucket = x / bucket_size;

    mini[bucket] = maxi[bucket] = sums[bucket] = 0;
    for (int i = std::min(n, (bucket + 1) * bucket_size) - 1; 
         i >= bucket * bucket_size; --i) {
      sums[bucket] += vals[i];
      maxi[bucket] = std::max(maxi[bucket], sums[bucket]);
      mini[bucket] = std::min(mini[bucket], sums[bucket]);
    }
  }

  std::tuple<int, int, int> query(int c) {
    int sufsum = 0, sufmin = 0, sufmax = 0;
    for (int bucket = bucket_cnt - 1; bucket >= 0; --bucket) {
      long long nsufsum = sufsum + sums[bucket],
                nsufmin = std::min(1LL * sufmin, sufsum + mini[bucket]),
                nsufmax = std::max(1LL * sufmax, sufsum + maxi[bucket]);
      if (nsufmax - nsufmin > c) {
        for (int i = std::min(n, (bucket + 1) * bucket_size) - 1; 
             i >= bucket * bucket_size; --i) {
          sufsum += vals[i];
          sufmin = std::min(sufmin, sufsum);
          sufmax = std::max(sufmax, sufsum);
          if (sufmax - sufmin > c) return std::make_tuple(sufmin, sufmax, i);
        }
      }
      sufsum = nsufsum; sufmax = nsufmax; sufmin = nsufmin;
    }
    return std::make_tuple(sufmin, sufmax, 0);
  }

  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);
  Buckets 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 1 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 28548 KB Output is correct
2 Correct 1053 ms 28544 KB Output is correct
3 Correct 1004 ms 29376 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 750 ms 14268 KB Output is correct
3 Correct 97 ms 14396 KB Output is correct
4 Correct 1106 ms 31388 KB Output is correct
5 Correct 1075 ms 31792 KB Output is correct
6 Correct 928 ms 32188 KB Output is correct
7 Correct 926 ms 31416 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 752 ms 11416 KB Output is correct
4 Correct 84 ms 13220 KB Output is correct
5 Correct 892 ms 24112 KB Output is correct
6 Correct 868 ms 24868 KB Output is correct
7 Correct 739 ms 25456 KB Output is correct
8 Correct 896 ms 24088 KB Output is correct
9 Correct 1063 ms 25468 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 952 ms 28548 KB Output is correct
7 Correct 1053 ms 28544 KB Output is correct
8 Correct 1004 ms 29376 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 750 ms 14268 KB Output is correct
11 Correct 97 ms 14396 KB Output is correct
12 Correct 1106 ms 31388 KB Output is correct
13 Correct 1075 ms 31792 KB Output is correct
14 Correct 928 ms 32188 KB Output is correct
15 Correct 926 ms 31416 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 752 ms 11416 KB Output is correct
19 Correct 84 ms 13220 KB Output is correct
20 Correct 892 ms 24112 KB Output is correct
21 Correct 868 ms 24868 KB Output is correct
22 Correct 739 ms 25456 KB Output is correct
23 Correct 896 ms 24088 KB Output is correct
24 Correct 1063 ms 25468 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 75 ms 13408 KB Output is correct
27 Correct 681 ms 14080 KB Output is correct
28 Correct 1039 ms 30160 KB Output is correct
29 Correct 893 ms 30428 KB Output is correct
30 Correct 872 ms 30616 KB Output is correct
31 Correct 943 ms 30812 KB Output is correct
32 Correct 852 ms 31020 KB Output is correct