Submission #217162

#	Time	Username	Problem	Language	Result	Execution time	Memory
217162		rama_pang	Sweeping (JOI20_sweeping)	C++14	100 / 100	8119 ms	787204 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;

class Sweeping {
 
 private:

  struct Point {
    int x, y;

    Point() {}
    Point(int x, int y) : x(x), y(y) {}
  };

  struct Operation {
    int L; // If the operation is of type H, L denotes (N - L[i]) for operation i. L is actually the x-coordinate of the bottomright corner of the triangle formed by the operation, not its length.
    bool vertical;

    Operation() {}
    Operation(int L, bool v) : L(L), vertical(v) {}

    bool IsVertical() { return vertical; }
    const bool IsVertical() const { return vertical; }
    bool operator < (const Operation &o) const { return make_pair(L, vertical) < make_pair(o.L, o.vertical); }
  };

  class SegmentTree { // Range Minimum Query
   
   private:

    int sz;
    vector<int> value;
    vector<int> tree;

    int pull(int a, int b) {
      if (a == -1) return b;
      if (b == -1) return a;
      return value[a] < value[b] ? a : b;
    }

   public:

    void Build(const vector<int> &val, const vector<int> &base) {
      sz = val.size();
      value = val;
      tree.resize(2 * sz);
      for (int i = 0; i < sz; i++) {
        tree[i + sz] = base[i];
      }
      for (int i = sz - 1; i >= 0; i--) {
        tree[i] = pull(tree[i * 2], tree[i * 2 + 1]);
      }
    }

    int Query(int l, int r) {
      int res = -1;
      for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
        if (l & 1) res = pull(res, tree[l++]);
        if (r & 1) res = pull(res, tree[--r]);
      }
      return res;
    }

  };

  class Transformation { // Given a set of operations Q, find out where point (x, y) will be after all operations
   
   private:

    int sz = 0;
    int N;
    bool isBuilt = false;

    vector<Operation> ops; // operations in chronological order
    vector<Operation> ops_sorted_L; // sorted by Operation.L

    SegmentTree rmq;

    void Unique() { // delete multiple elements (since they don't have any effect anyways and make implementation harder)
      vector<Operation> new_ops;
      set<Operation> unique_ops;
      for (int i = 0; i < sz; i++) {
        if (unique_ops.count(ops[i]) == 1) {
          continue;
        }
        new_ops.emplace_back(ops[i]);
        unique_ops.emplace(ops[i]);
      }
      ops = new_ops;
      sz = ops.size();
    }

    void Build() {
      Unique();
      
      vector<vector<int>> adj(sz);
      function<void(int, vector<int>&)> dfs = [&](int u, vector<int> &postorder) {
        for (auto &v : adj[u]) dfs(v, postorder); // to compute the minimum value easily. See further for details.
        postorder.emplace_back(u);
      };
      
      vector<int> roots;

      set<pair<Operation, int>> triangles; // (Operation, time in chronological order)
      for (int i = 0; i < sz; i++) {
        auto it = triangles.lower_bound(make_pair(ops[i], i));
        bool isRoot = true;

        if (it != end(triangles)) {
          if (ops[i].IsVertical() && (*it).first.IsVertical()) { 
            // if there is an operation H that results in same coordinate, we do not consider it since 
            // it forms a dot as their triangle, and there is no connection between that dot and curent 
            // operation, Incidentally, sorting means that an operation H will be encountered in that 
            // very case, so we do not need to worry about it.
            
            adj[(*it).second].emplace_back(i); // swapping i and it will make no difference - take the one with higher finak y-coordinate.
            isRoot = false;
          }
        }

        if (it != begin(triangles)) { 
          it--;
          if (!ops[i].IsVertical() && !(*it).first.IsVertical()) {
            // if there is an operation V that results in same coordinate, we do not consider it since 
            // it forms a dot as their triangle, and there is no connection between that dot and curent 
            // operation. Incidentally, sorting means that an operation V will be encountered in that 
            // very case, so we do not need to worry about it.

            adj[(*it).second].emplace_back(i);
            isRoot = false;
          }
        }

        if (isRoot) {
          roots.emplace_back(i);
        }

        triangles.emplace(ops[i], i);
      }

      vector<int> new_chronological_order;
      for (auto &r : roots) {
        dfs(r, new_chronological_order); // postorder dfs
      }

      vector<int> when(sz), base;
      for (int i = 0; i < sz; i++) {
        when[new_chronological_order[i]] = i; // compute time values for every indices
      }

      for (auto &t : triangles) {
        ops_sorted_L.emplace_back(t.first); // operation sorted by L
        base.emplace_back(t.second); // indices
      }

      rmq.Build(when, base);
      return;
    }

    Point Transform_(Point p) {
      int l = lower_bound(begin(ops_sorted_L), end(ops_sorted_L), Operation(p.x, false)) - begin(ops_sorted_L);
      int r = upper_bound(begin(ops_sorted_L), end(ops_sorted_L), Operation(N - p.y, true)) - begin(ops_sorted_L) - 1;
      if (l > r) return p;

      // [l, r] are regions p can potentially end up in
      int mn = rmq.Query(l, r);
      if (ops[mn].IsVertical()) {
        if (p.x <= ops[mn].L) p.y = max(p.y, N - ops[mn].L);
      } else {
        if (p.y <= N - ops[mn].L) p.x = max(p.x, ops[mn].L); // ops[mn].L = N - L[i], so L[i] = N - pos[mn].L
      }

      // update [l, r] after being swept by operation mn
      int mn_loc = lower_bound(begin(ops_sorted_L), end(ops_sorted_L), ops[mn]) - begin(ops_sorted_L); // where mn is in ops_sorted_L
      if (ops[mn].IsVertical()) {
        r = mn_loc - 1; // first is operation V, then operation H
      } else {
        l = mn_loc + 1; // first is operation H, then operation V
      }
      if (l > r) return p;

      // there is one more operation (if previous is H, then now it's V; vice versa)
      mn = rmq.Query(l, r);
      if (ops[mn].IsVertical()) {
        if (p.x <= ops[mn].L) p.y = max(p.y, N - ops[mn].L);
      } else {
        if (p.y <= N - ops[mn].L) p.x = max(p.x, ops[mn].L); // ops[mn].L = N - L[i], so L[i] = N - ops[mn].L
      }

      return p;
    }

   public:

    Transformation() {}
    Transformation(int N) : N(N) {}

    void AddOperation(const Operation &o) {
      ops.emplace_back(o); sz++;
    }

    Point Transform(Point p) {
      if (!isBuilt) isBuilt = true, Build();
      return Transform_(p);
    }

  };

  class QueryTree {
   
   private:

    int sz;
    vector<Transformation> tree;

    void AddOperation(int n, int tl, int tr, int pos, const Operation &op) {
      tree[n].AddOperation(op);
      if (tl == tr) return;
      int mid = (tl + tr) / 2;
      if (pos <= mid) {
        AddOperation(n * 2, tl, mid, pos, op);
      } else {
        AddOperation(n * 2 + 1, mid + 1, tr, pos, op);
      }
    }

    void Query(int n, int tl, int tr, int l, int r, Point &p) {
      if (tr < l || r < tl || tl > tr || l > r) return;
      if (l <= tl && tr <= r) return void(p = tree[n].Transform(p));
      int mid = (tl + tr) / 2;
      Query(n * 2, tl, mid, l, r, p);
      Query(n * 2 + 1, mid + 1, tr, l, r, p);
    }

   public:
  
    QueryTree(int N, int Q) {
      sz = Q;
      tree.assign(4 * sz, Transformation(N));
    }

    void AddOperation(int pos, Operation op) {
      AddOperation(1, 0, sz - 1, pos, op);
    }

    Point Query(int l, int r, Point p) {
      Query(1, 0, sz - 1, l, r, p);
      return p;
    }

  };

 public:

  void Solve() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int N, M, Q;
    vector<pair<Point, int>> P; // (Point, time_added)

    cin >> N >> M >> Q;

    QueryTree QTree(N, Q);

    for (int i = 0; i < M; i++) {
      int x, y; cin >> x >> y;
      P.emplace_back(Point(x, y), 0);
    }

    for (int i = 0, op_cnt = 0; i < Q; i++) {
      int T; cin >> T;

      if (T == 1) {
        int pos; cin >> pos; pos--;
        Point res = QTree.Query(P[pos].second, op_cnt - 1, P[pos].first);
        cout << res.x << " " << res.y << "\n";
      } else if (T == 2 || T == 3) {
        int L; cin >> L;
        if (T == 2) QTree.AddOperation(op_cnt, Operation(N - L, false)); // operation H
        if (T == 3) QTree.AddOperation(op_cnt, Operation(L, true)); // operation V
        op_cnt++;
      } else if (T == 4) {
        int x, y; cin >> x >> y;
        P.emplace_back(Point(x, y), op_cnt);
      }
    }
  }

};

int main() {
  Sweeping Solver;
  Solver.Solve();
  return 0;  
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25