제출 #1056037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1056037		erray	사탕 분배 (IOI21_candies)	C++17	32 / 100	5085 ms	64548 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, tag;
  int n;
  SegTree(int _n) : n(_n) {
    tree.resize(2 * n - 1);
    tag.resize(2 * n - 1);
  }
  void apply(int v, T x) {
    tree[v] = unite(tree[v], x);
    tag[v] = unite(tag[v], x);
  }
  void push(int v, int l, int r) {
    def;
    apply(v + 1, tag[v]);
    apply(rv, tag[v]);
    tag[v] = T{};
  }
  void modify(int v, int l, int r, int ll, int rr, T x) {
    if (l >= ll && rr >= r) {
      apply(v, x);
      return;
    }
    def;
    push(v, l, r);
    if (ll <= mid) {
      modify(v + 1, l, mid, ll, rr, x);
    }
    if (mid < rr) {
      modify(rv, mid + 1, r, ll, rr, x);
    }
  }
  void modify(int ll, int rr, int x) {
    modify(0, 0, n - 1, ll, rr, T(x));
  }
  T get(int p) {
    int v = 0, l = 0, r = n - 1;
    while (l < r) {
      def;
      push(v, l, r);
      if (p <= mid) {
        v = v + 1;
        r = mid;
      } else {
        v = rv;
        l = mid + 1;
      }
    }
    return tree[v];
  }
};

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<tuple<int, int, vector<int>>> queries;
  queries.emplace_back(0, q, vector<int>{});
  for (int i = 0; i < n; ++i) get<2>(queries.back()).push_back(i);
  vector<int> first(n);
  while (!queries.empty()) {
    vector<bool> res(n);
    vector<vector<int>> ask(q);
    for (auto[l, r, v] : queries) {
      debug(l, r, v);
      if (l == r) {
        for (auto i : v) {
          first[i] = l;
        }
      } else {
        int mid = (l + r) >> 1;
        for (auto i : v) ask[mid].push_back(i);
      }
    }
    SegTree st(n);
    for (int i = q - 1; i >= 0; --i) {
      st.modify(l[i], r[i], v[i]);
      for (auto i : ask[i]) {
        res[i] = st.get(i).compressed() < c[i];
      }
    }
    vector<tuple<int, int, vector<int>>> new_queries;
    for (auto[l, r, v] : queries) {
      if (l == r) continue;
      int mid = (l + r) >> 1;
      array<vector<int>, 2> to;
      for (auto i : v) {
        to[res[i]].push_back(i);
      }
      new_queries.emplace_back(l, mid, to[1]);
      new_queries.emplace_back(mid + 1, r, to[0]);
    }
    swap(new_queries, queries);
  }
  vector<vector<int>> ask(q + 1);
  for (int i = 0; i < n; ++i) {
    ask[first[i]].push_back(i);
  }
  vector<int> ans(n);
  SegTree st(n);
  for (int i = q - 1; i >= 0; --i) {
    for (auto x : ask[i + 1]) {
      auto n = st.get(x);
      if (v[i] > 0) {
        ans[x] = c[x] - n.upper.compressed;
      } else {
        ans[x] = n.lower.compressed;
      }
    }
    st.modify(l[i], r[i], v[i]);
  }
  for (auto i : ask[0]) {
    ans[i] = st.get(i).lower.compressed;
  }
  return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33