Submission #1056111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056111		erray	Distributing Candies (IOI21_candies)	C++17	100 / 100	350 ms	36688 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33