oj.uz

Submission #434980

# Submission time Handle Problem Language Result Execution time Memory
434980 2021-06-22T17:20:30 Z model_code Distributing Candies (IOI21_candies) C++17
100 / 100
 1233 ms 25556 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 5 ms 460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1034 ms 25468 KB Output is correct
2 Correct 1082 ms 25552 KB Output is correct
3 Correct 1187 ms 25516 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 779 ms 11444 KB Output is correct
3 Correct 112 ms 12200 KB Output is correct
4 Correct 1233 ms 25460 KB Output is correct
5 Correct 1138 ms 25468 KB Output is correct
6 Correct 1029 ms 25556 KB Output is correct
7 Correct 1016 ms 25460 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 332 KB Output is correct
3 Correct 759 ms 9032 KB Output is correct
4 Correct 81 ms 12100 KB Output is correct
5 Correct 912 ms 20660 KB Output is correct
6 Correct 871 ms 20648 KB Output is correct
7 Correct 839 ms 20668 KB Output is correct
8 Correct 915 ms 20652 KB Output is correct
9 Correct 1156 ms 20664 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 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 1034 ms 25468 KB Output is correct
7 Correct 1082 ms 25552 KB Output is correct
8 Correct 1187 ms 25516 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 779 ms 11444 KB Output is correct
11 Correct 112 ms 12200 KB Output is correct
12 Correct 1233 ms 25460 KB Output is correct
13 Correct 1138 ms 25468 KB Output is correct
14 Correct 1029 ms 25556 KB Output is correct
15 Correct 1016 ms 25460 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 759 ms 9032 KB Output is correct
19 Correct 81 ms 12100 KB Output is correct
20 Correct 912 ms 20660 KB Output is correct
21 Correct 871 ms 20648 KB Output is correct
22 Correct 839 ms 20668 KB Output is correct
23 Correct 915 ms 20652 KB Output is correct
24 Correct 1156 ms 20664 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 91 ms 12072 KB Output is correct
27 Correct 769 ms 11468 KB Output is correct
28 Correct 1090 ms 25464 KB Output is correct
29 Correct 1068 ms 25464 KB Output is correct
30 Correct 1022 ms 25540 KB Output is correct
31 Correct 1082 ms 25464 KB Output is correct
32 Correct 1002 ms 25468 KB Output is correct