Submission #1280356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280356		avighna	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	435 ms	114764 KiB

constellation3

#include <bits/stdc++.h>

template <typename T>
class segment_tree {
private:
  std::size_t _n, n;
  std::vector<T> seg;

public:
  segment_tree(std::size_t _n) : _n(_n), n(std::bit_ceil(_n)), seg(2 * n) {}
  void set(std::size_t i, const T &x) {
    for (seg[i += n] = x, i /= 2; i > 0; i /= 2) {
      seg[i] = seg[2 * i] + seg[2 * i + 1];
    }
  }
  T query(std::size_t l, std::size_t r) const {
    T ans_l = T{}, ans_r = T{};
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1)
        ans_l = ans_l + seg[l++];
      if (r & 1)
        ans_r = seg[--r] + ans_r;
    }
    return ans_l + ans_r;
  }
  const T &at(std::size_t i) const { return seg[n + i]; }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n;
  std::cin >> n;
  std::vector<int> a(n);
  struct node {
    int x, i;
    node(int x, int i) : x(x), i(i) {}
    node() : x(-1), i(-1) {}
    node operator+(const node &other) const {
      if (x != other.x) {
        return x > other.x ? *this : other;
      }
      return i < other.i ? *this : other;
    }
  };
  segment_tree<node> st(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
    st.set(i, {a[i], i});
  }

  auto iterate = [&](int ql, int qr, int qx) {
    std::vector<int> ans;
    int l = ql;
    while (l <= qr) {
      auto [x, i] = st.query(l, qr);
      if (x != qx) {
        break;
      }
      ans.push_back(i);
      l = i + 1;
    }
    return ans;
  };

  struct node_info {
    int l, r; // left and right intervals of the node
    int s, e; // for example, starts from height n+1 and ends at height n-2 (as arrays)
  };
  std::vector<node_info> info(n);
  std::vector<std::vector<int>> adj(n + 1); // stores the cartesian tree
  struct point {
    int x, y, c;
  };
  std::vector<std::vector<point>> points(n + 1); // points associated with a node in the cartesian tree
  info[0] = {.l = 0, .r = n - 1, .s = n + 1};
  // when we enter a node, we know l,r,s, and don't know e, which we need to find out
  int label = 0; // marker for the node we're currently at
  auto build = [&](auto &&self, int u) {
    auto [qx, qi] = st.query(info[u].l, info[u].r);
    info[u].e = qx + 1;
    if (info[u].l == info[u].r) { // base case when we're at the leaf
      return;
    }
    int x = qx, i = qi;
    int l = info[u].l;
    auto vals = iterate(info[u].l, info[u].r, x);
    vals.push_back(info[u].r + 1);
    for (int &pos : vals) {
      if (l > pos - 1) {
        l = pos + 1;
        continue;
      }
      int to = label++;
      adj[u].push_back(to);
      info[to].l = l, info[to].r = pos - 1;
      info[to].s = x;
      self(self, to);
      l = pos + 1;
    }
  };
  build(build, label++);

  // search up, for each point, which cartesian tree node it is part of
  struct rect {
    int x1, y1, x2, y2, i;
  };
  std::vector<rect> rects(label);
  for (int i = 0; i < label; ++i) {
    rects[i] = {.x1 = info[i].l, .y1 = info[i].e, .x2 = info[i].r, .y2 = info[i].s, .i = i};
  }
  // need to build an offline sweep data structure
  int m;
  std::cin >> m;
  int64_t tot = 0;
  struct raw_point {
    int x, y;
    bool operator<(const raw_point &other) const {
      if (x != other.x) {
        return x < other.x;
      }
      return y < other.y;
    }
  };
  std::vector<point> inp_points;
  std::vector<raw_point> buf; // buf is the set of queries
  for (int i = 0, x, y, c; i < m; ++i) {
    std::cin >> x >> y >> c;
    --x;
    buf.push_back({x, y});
    inp_points.push_back({x, y, c});
    tot += c;
    buf.push_back({x, a[x] + 1}); // we'd wanna queries demotes as well
  }

  struct rect_in {
    std::vector<rect> rects;
    std::vector<raw_point> buf;
    std::vector<int> ans;
    int n;

    rect_in(std::vector<rect> _rects, std::vector<raw_point> _buf) : n(_buf.size()), rects(_rects), buf(_buf), ans(_buf.size(), -1) {
      std::sort(buf.begin(), buf.end());

      struct event {
        int type; // 0: add, 1: query, 2: remove
        int x, i;
        bool operator<(const event &other) const {
          if (x != other.x) {
            return x < other.x;
          }
          return type < other.type;
        }
      };
      std::vector<event> events;
      for (int i = 0; i < rects.size(); ++i) {
        events.push_back({.type = 0, .x = rects[i].x1, .i = i});
        events.push_back({.type = 2, .x = rects[i].x2 + 1, .i = i});
      }
      for (int i = 0; i < n; ++i) {
        events.push_back({.type = 1, .x = buf[i].x, .i = i});
      }

      std::sort(events.begin(), events.end());

      std::set<std::pair<int, int>> ys; // active y vals
      for (auto &[type, x, i] : events) {
        if (type == 0) {
          ys.insert({rects[i].y1, i});
        } else if (type == 1) {
          std::pair<int, int> p = {buf[i].y, std::numeric_limits<int>::max()};
          auto it = ys.upper_bound(p);
          --it;
          ans[i] = it->second;
        } else {
          ys.erase({rects[i].y1, i});
        }
      }
    }

    int query(int x, int y) {
      raw_point p{x, y};
      auto it = std::lower_bound(buf.begin(), buf.end(), p);
      return ans[it - buf.begin()];
    }
  };
  rect_in sweep(rects, buf);

  // add the points belonging to each rectangle
  for (int i = 0; i < m; ++i) {
    auto [x, y, c] = inp_points[i];
    points[sweep.query(x, y)].push_back({x, y, c});
  }

  // perform an euler tour on the cartesian tree
  std::vector<int> in(label), out(label);
  int timer = 0;
  auto dfs_euler = [&](auto &&self, int u) -> void {
    in[u] = timer++;
    for (int &i : adj[u]) {
      self(self, i);
    }
    out[u] = timer - 1;
  };
  dfs_euler(dfs_euler, 0); // now the subtree of u is [start[u], end[u]]

  segment_tree<int64_t> path_st(label + 1); // a difference array segtree
  auto add = [&](int u, int64_t x) {
    path_st.set(in[u], path_st.at(in[u]) + x);
    path_st.set(out[u] + 1, path_st.at(out[u] + 1) - x);
  };
  auto query_from_root = [&](int u) {
    return path_st.query(0, in[u]);
  };
  auto query = [&](int low, int high) { // needs high to be a parent of low
    return query_from_root(low) - query_from_root(high);
  };

  std::vector<int64_t> dp(label), dpsum(label); // dpsum is the sum of the dps of each child
  // dp[u] = the sum of paths *starting at u*
  for (int u = label - 1; u >= 0; --u) {
    for (int &i : adj[u]) {
      dpsum[u] += dpsum[i];
    }
    for (auto &[x, y, c] : points[u]) {
      dp[u] = std::max(dp[u], c - query(sweep.query(x, a[x] + 1), u));
    }
    add(u, dp[u]);
    dpsum[u] += dp[u];
  }

  std::cout << tot - dpsum[0] << '\n';
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65