oj.uz

Submission #1056111

# Submission time Handle Problem Language Result Execution time Memory
1056111 2024-08-13T07:50:37 Z erray Distributing Candies (IOI21_candies) C++17
100 / 100
 350 ms 36688 KB 
#include "candies.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/hp/contests/debug.h"
#else 
  #define debug(...) void(37)
#endif

struct mapping {
  int64_t dist = 0;
  int64_t compressed = 0;
};
mapping unite(mapping l, mapping r) {
  mapping res;
  int64_t start = max(r.compressed, l.dist);
  res.compressed = l.compressed + start - l.dist;
  res.dist = r.dist + start - r.compressed;
  return res;
}
struct two_sided_mapping {
  mapping lower, upper;
  two_sided_mapping() { } 
  two_sided_mapping(const int& x) {
    lower = upper = mapping{};
    if (x > 0) {
      lower.compressed = x;
      upper.dist = x;
    } else {
      upper.compressed = -x;
      lower.dist = -x;
    }
  }
  int64_t compressed() {
    return lower.compressed + upper.compressed;
  }
};

two_sided_mapping unite(two_sided_mapping l, two_sided_mapping r) {
  l.lower = unite(l.lower, r.lower);
  l.upper = unite(l.upper, r.upper);
  return l;
}

using T = two_sided_mapping;

#define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
struct SegTree {
  vector<T> tree;
  int n;
  SegTree(int _n) : n(_n) {
    tree.resize(2 * n - 1);
  }
  void modify(int v, int l, int r, int p, T x) {
    if (l == r) {
      tree[v] = x;
      return;
    }
    def;
    if (p <= mid) {
      modify(v + 1, l, mid, p, x);
    } else {
      modify(rv, mid + 1, r, p, x);
    }
    tree[v] = unite(tree[rv], tree[v + 1]);
  }
  void modify(int p, int x) {
    modify(0, 0, n - 1, p, T(x));
  }
  pair<int, T> find_last(int cap) {
    int v = 0, l = 0, r = n - 1;
    T res;
    while (l < r) {
      def;
      auto test = unite(res, tree[rv]);
      if (test.compressed() < cap) {
        swap(res, test);
        v = v + 1;
        r = mid;
      } else {
        v = rv;
        l = mid + 1;
      }
    }
    auto test = unite(res, tree[v]);
    if (test.compressed() < cap) {
      --l;
      assert(l == -1);
      swap(test, res);
    }
    return {l, res};
  }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
  int n = int(c.size());
  int q = int(l.size());
  vector<vector<int>> events(n + 1);
  for (int i = 0; i < q; ++i) {
    events[l[i]].push_back(i);
    events[r[i] + 1].push_back(~i);
  }
  SegTree act(q + 1);
  vector<int> ans(n);
  for (int i = 0; i < n; ++i) {
    for (auto x : events[i]) {
      if (x >= 0) {
        act.modify(x, v[x]);
      } else {
        act.modify(~x, 0);
      }
    }
    auto[last, res] = act.find_last(c[i]);
    if (last == -1) {
      ans[i] = res.lower.compressed;
    } else if (v[last] > 0) {
      ans[i] = c[i] - res.upper.compressed;
    } else {
      ans[i] = res.lower.compressed;
    }
  }
  return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 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 292 ms 34896 KB Output is correct
2 Correct 298 ms 33900 KB Output is correct
3 Correct 350 ms 34104 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 198 ms 23016 KB Output is correct
3 Correct 56 ms 9804 KB Output is correct
4 Correct 286 ms 35836 KB Output is correct
5 Correct 301 ms 36052 KB Output is correct
6 Correct 308 ms 36688 KB Output is correct
7 Correct 303 ms 35668 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 73 ms 21948 KB Output is correct
4 Correct 41 ms 8764 KB Output is correct
5 Correct 119 ms 30012 KB Output is correct
6 Correct 128 ms 30612 KB Output is correct
7 Correct 126 ms 30912 KB Output is correct
8 Correct 120 ms 29888 KB Output is correct
9 Correct 119 ms 31164 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 292 ms 34896 KB Output is correct
7 Correct 298 ms 33900 KB Output is correct
8 Correct 350 ms 34104 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 198 ms 23016 KB Output is correct
11 Correct 56 ms 9804 KB Output is correct
12 Correct 286 ms 35836 KB Output is correct
13 Correct 301 ms 36052 KB Output is correct
14 Correct 308 ms 36688 KB Output is correct
15 Correct 303 ms 35668 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 73 ms 21948 KB Output is correct
19 Correct 41 ms 8764 KB Output is correct
20 Correct 119 ms 30012 KB Output is correct
21 Correct 128 ms 30612 KB Output is correct
22 Correct 126 ms 30912 KB Output is correct
23 Correct 120 ms 29888 KB Output is correct
24 Correct 119 ms 31164 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 42 ms 8892 KB Output is correct
27 Correct 172 ms 22620 KB Output is correct
28 Correct 303 ms 34656 KB Output is correct
29 Correct 254 ms 35156 KB Output is correct
30 Correct 313 ms 35384 KB Output is correct
31 Correct 298 ms 35408 KB Output is correct
32 Correct 275 ms 35668 KB Output is correct