oj.uz

답안 #1056037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1056037 2024-08-13T07:23:37 Z erray 사탕 분배 (IOI21_candies) C++17
32 / 100
 5000 ms 64548 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, 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.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 12 ms 572 KB Output is correct
5 Correct 36 ms 988 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5070 ms 58384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 3378 ms 34272 KB Output is correct
3 Correct 1581 ms 35584 KB Output is correct
4 Execution timed out 5085 ms 48768 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 169 ms 33280 KB Output is correct
4 Correct 1605 ms 44616 KB Output is correct
5 Correct 2835 ms 64548 KB Output is correct
6 Correct 2750 ms 63696 KB Output is correct
7 Correct 2405 ms 62548 KB Output is correct
8 Correct 2665 ms 63860 KB Output is correct
9 Correct 2474 ms 64244 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 12 ms 572 KB Output is correct
5 Correct 36 ms 988 KB Output is correct
6 Execution timed out 5070 ms 58384 KB Time limit exceeded
7 Halted 0 ms 0 KB -