oj.uz

Submission #217162

# Submission time Handle Problem Language Result Execution time Memory
217162 2020-03-29T07:09:31 Z rama_pang Sweeping (JOI20_sweeping) C++14
100 / 100
 8119 ms 787204 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3456 KB Output is correct
2 Correct 21 ms 3712 KB Output is correct
3 Correct 8 ms 2944 KB Output is correct
4 Correct 18 ms 3456 KB Output is correct
5 Correct 10 ms 3456 KB Output is correct
6 Correct 11 ms 3328 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7211 ms 737960 KB Output is correct
2 Correct 6897 ms 754444 KB Output is correct
3 Correct 6736 ms 754568 KB Output is correct
4 Correct 5083 ms 753132 KB Output is correct
5 Correct 5246 ms 770024 KB Output is correct
6 Correct 2999 ms 624836 KB Output is correct
7 Correct 7783 ms 754448 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6410 ms 787204 KB Output is correct
2 Correct 5922 ms 768968 KB Output is correct
3 Correct 4658 ms 763724 KB Output is correct
4 Correct 4687 ms 711248 KB Output is correct
5 Correct 7543 ms 769276 KB Output is correct
6 Correct 7594 ms 767912 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6410 ms 787204 KB Output is correct
2 Correct 5922 ms 768968 KB Output is correct
3 Correct 4658 ms 763724 KB Output is correct
4 Correct 4687 ms 711248 KB Output is correct
5 Correct 7543 ms 769276 KB Output is correct
6 Correct 7594 ms 767912 KB Output is correct
7 Correct 5486 ms 702736 KB Output is correct
8 Correct 5326 ms 703076 KB Output is correct
9 Correct 5173 ms 703060 KB Output is correct
10 Correct 4323 ms 702536 KB Output is correct
11 Correct 4854 ms 710880 KB Output is correct
12 Correct 7570 ms 767804 KB Output is correct
13 Correct 6102 ms 702916 KB Output is correct
14 Correct 1066 ms 682824 KB Output is correct
15 Correct 872 ms 501852 KB Output is correct
16 Correct 6298 ms 702552 KB Output is correct
17 Correct 3046 ms 656664 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3456 KB Output is correct
2 Correct 21 ms 3712 KB Output is correct
3 Correct 8 ms 2944 KB Output is correct
4 Correct 18 ms 3456 KB Output is correct
5 Correct 10 ms 3456 KB Output is correct
6 Correct 11 ms 3328 KB Output is correct
7 Correct 7211 ms 737960 KB Output is correct
8 Correct 6897 ms 754444 KB Output is correct
9 Correct 6736 ms 754568 KB Output is correct
10 Correct 5083 ms 753132 KB Output is correct
11 Correct 5246 ms 770024 KB Output is correct
12 Correct 2999 ms 624836 KB Output is correct
13 Correct 7783 ms 754448 KB Output is correct
14 Correct 6410 ms 787204 KB Output is correct
15 Correct 5922 ms 768968 KB Output is correct
16 Correct 4658 ms 763724 KB Output is correct
17 Correct 4687 ms 711248 KB Output is correct
18 Correct 7543 ms 769276 KB Output is correct
19 Correct 7594 ms 767912 KB Output is correct
20 Correct 5486 ms 702736 KB Output is correct
21 Correct 5326 ms 703076 KB Output is correct
22 Correct 5173 ms 703060 KB Output is correct
23 Correct 4323 ms 702536 KB Output is correct
24 Correct 4854 ms 710880 KB Output is correct
25 Correct 7570 ms 767804 KB Output is correct
26 Correct 6102 ms 702916 KB Output is correct
27 Correct 1066 ms 682824 KB Output is correct
28 Correct 872 ms 501852 KB Output is correct
29 Correct 6298 ms 702552 KB Output is correct
30 Correct 3046 ms 656664 KB Output is correct
31 Correct 5893 ms 752676 KB Output is correct
32 Correct 7251 ms 754168 KB Output is correct
33 Correct 7041 ms 754112 KB Output is correct
34 Correct 6805 ms 736068 KB Output is correct
35 Correct 6455 ms 736060 KB Output is correct
36 Correct 5646 ms 734192 KB Output is correct
37 Correct 6276 ms 763712 KB Output is correct
38 Correct 7813 ms 744608 KB Output is correct
39 Correct 8119 ms 738004 KB Output is correct
40 Correct 8105 ms 754220 KB Output is correct