oj.uz

Submission #216398

# Submission time Handle Problem Language Result Execution time Memory
216398 2020-03-27T09:08:36 Z IOrtroiii Sweeping (JOI20_sweeping) C++14
100 / 100
 7884 ms 357200 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500500 * 3;

int N, M, Q;
int pc = 0;
pair<int, int> pts[MAXN];
pair<int, int> ans[MAXN];
bool moved[MAXN];

struct Solver {
   int root[MAXN];
   vector<int> vals;
   vector<vector<int>> comps;
   void reset() {
      vals.clear();
      comps.clear();
   }
   int add(int val, int realId) {
      int id = int(vals.size());
      vals.emplace_back(val);
      comps.emplace_back();
      if (realId != -1) {
         root[realId] = id;
         comps[id].emplace_back(realId);
      }
      return id;
   }
   int merge(int v, int u) {
      if (int(comps[v].size()) < int(comps[u].size())) {
         swap(v, u);
      }
      vals[v] = max(vals[v], vals[u]);
      for (int z : comps[u]) {
         root[z] = v;
         comps[v].emplace_back(z);
      }
      return v;
   }
   int value(int x) { return vals[root[x]]; }
} xs, ys;

void getReal(int id) {
   pts[id].first = xs.value(id);
   pts[id].second = ys.value(id);
}

void solve(int x, int y, vector<tuple<int, int, int>> qs) {
   if (qs.empty()) return;
   int len = N - x - y;
   if (!len) {
      for (auto q : qs) {
         if (get<0>(q) == 1) {
            ans[get<2>(q)] = {x, y};
         }
      }
      return;
   }
   int nx = x + (len + 1) / 2;
   int ny = y + (len + 2) / 2;
   vector<tuple<int, int, int>> uq;
   vector<tuple<int, int, int>> rq;
   multiset<pair<int, int>> xms;
   multiset<pair<int, int>> yms;
   xs.reset(), ys.reset();
   for (auto q : qs) {
      if (get<0>(q) == 1) {
         int pid = get<1>(q);
         int qid = get<2>(q);
         if (pts[pid].second >= ny) {
            uq.emplace_back(q);
         } else if (pts[pid].first >= nx) {
            rq.emplace_back(q);
         } else {
            getReal(pid);
            ans[qid] = pts[pid];
         }
      } else if (get<0>(q) == 2) {
         int len = get<1>(q);
         if (len >= ny) {
            int nv = xs.add(N - len, -1);
            while (xms.size() && xms.begin()->first <= N - len) {
               int v = xms.begin()->second;
               xms.erase(xms.begin());
               nv = xs.merge(nv, v);
            }
            uq.emplace_back(q);
            xms.emplace(xs.vals[nv], nv);
         } else {
            while (yms.size() && yms.begin()->first <= len) {
               int v = yms.begin()->second;
               yms.erase(yms.begin());
               for (int z : ys.comps[v]) {
                  if (!moved[z]) {
                     moved[z] = true;
                     getReal(z);
                     pts[z].first = N - len;
                     rq.emplace_back(4, z, 0);
                  }
               }
            }
            rq.emplace_back(q);
         }
      } else if (get<0>(q) == 3) {
         int len = get<1>(q);
         if (len >= nx) {
            int nv = ys.add(N - len, -1);
            while (yms.size() && yms.begin()->first <= N - len) {
               int v = yms.begin()->second;
               yms.erase(yms.begin());
               nv = ys.merge(nv, v);
            }
            rq.emplace_back(q);
            yms.emplace(ys.vals[nv], nv);
         } else {
            while (xms.size() && xms.begin()->first <= len) {
               int v = xms.begin()->second;
               xms.erase(xms.begin());
               for (int z : xs.comps[v]) {
                  if (!moved[z]) {
                     moved[z] = true;
                     getReal(z);
                     pts[z].second = N - len;
                     uq.emplace_back(4, z, 0);
                  }
               }
            }
            uq.emplace_back(q);
         }
      } else {
         int z = get<1>(q);
         moved[z] = false;
         if (pts[z].second >= ny) {
            moved[z] = true;
            uq.emplace_back(q);
         } else if (pts[z].first >= nx) {
            moved[z] = true;
            rq.emplace_back(q);
         } else {
            int xv = xs.add(pts[z].first, z);
            int yv = ys.add(pts[z].second, z);
            xms.emplace(xs.vals[xv], xv);
            yms.emplace(ys.vals[yv], yv);
         }
      }
   }
   solve(x, ny, uq);
   solve(nx, y, rq);
}

vector<int> asks;

int main() {
   ios_base::sync_with_stdio(false);
   cin >> N >> M >> Q;
   vector<tuple<int, int, int>> qs;
   for (int i = 1; i <= M; ++i) {
      int x, y;
      cin >> x >> y;
      pts[++pc] = {x, y};
      qs.emplace_back(4, pc, 0);
   }
   for (int i = 1; i <= Q; ++i) {
      int op;
      cin >> op;
      if (op == 1) {
         int id;
         cin >> id;
         qs.emplace_back(1, id, i);
         asks.emplace_back(i);
      } else if (op < 4) {
         int len;
         cin >> len;
         qs.emplace_back(op, len, 0);
      } else {
         int x, y;
         cin >> x >> y;
         pts[++pc] = {x, y};
         qs.emplace_back(4, pc, 0);
      }
   }
   solve(0, 0, qs);
   for (int id : asks) {
      cout << ans[id].first << " " << ans[id].second << "\n";
   }
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1408 KB Output is correct
2 Correct 17 ms 916 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 18 ms 1348 KB Output is correct
5 Correct 16 ms 1408 KB Output is correct
6 Correct 7 ms 1280 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3888 ms 135016 KB Output is correct
2 Correct 3759 ms 148440 KB Output is correct
3 Correct 3728 ms 148984 KB Output is correct
4 Correct 4582 ms 243372 KB Output is correct
5 Correct 7254 ms 203204 KB Output is correct
6 Correct 5403 ms 194976 KB Output is correct
7 Correct 3668 ms 148468 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4149 ms 159700 KB Output is correct
2 Correct 4271 ms 169628 KB Output is correct
3 Correct 3981 ms 213980 KB Output is correct
4 Correct 4872 ms 314736 KB Output is correct
5 Correct 4752 ms 246656 KB Output is correct
6 Correct 3779 ms 171392 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4149 ms 159700 KB Output is correct
2 Correct 4271 ms 169628 KB Output is correct
3 Correct 3981 ms 213980 KB Output is correct
4 Correct 4872 ms 314736 KB Output is correct
5 Correct 4752 ms 246656 KB Output is correct
6 Correct 3779 ms 171392 KB Output is correct
7 Correct 3956 ms 158204 KB Output is correct
8 Correct 3931 ms 163116 KB Output is correct
9 Correct 3949 ms 154980 KB Output is correct
10 Correct 5012 ms 228304 KB Output is correct
11 Correct 4936 ms 278980 KB Output is correct
12 Correct 6054 ms 209904 KB Output is correct
13 Correct 6407 ms 330308 KB Output is correct
14 Correct 168 ms 47936 KB Output is correct
15 Correct 1603 ms 145840 KB Output is correct
16 Correct 3790 ms 162604 KB Output is correct
17 Correct 3770 ms 160740 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1408 KB Output is correct
2 Correct 17 ms 916 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 18 ms 1348 KB Output is correct
5 Correct 16 ms 1408 KB Output is correct
6 Correct 7 ms 1280 KB Output is correct
7 Correct 3888 ms 135016 KB Output is correct
8 Correct 3759 ms 148440 KB Output is correct
9 Correct 3728 ms 148984 KB Output is correct
10 Correct 4582 ms 243372 KB Output is correct
11 Correct 7254 ms 203204 KB Output is correct
12 Correct 5403 ms 194976 KB Output is correct
13 Correct 3668 ms 148468 KB Output is correct
14 Correct 4149 ms 159700 KB Output is correct
15 Correct 4271 ms 169628 KB Output is correct
16 Correct 3981 ms 213980 KB Output is correct
17 Correct 4872 ms 314736 KB Output is correct
18 Correct 4752 ms 246656 KB Output is correct
19 Correct 3779 ms 171392 KB Output is correct
20 Correct 3956 ms 158204 KB Output is correct
21 Correct 3931 ms 163116 KB Output is correct
22 Correct 3949 ms 154980 KB Output is correct
23 Correct 5012 ms 228304 KB Output is correct
24 Correct 4936 ms 278980 KB Output is correct
25 Correct 6054 ms 209904 KB Output is correct
26 Correct 6407 ms 330308 KB Output is correct
27 Correct 168 ms 47936 KB Output is correct
28 Correct 1603 ms 145840 KB Output is correct
29 Correct 3790 ms 162604 KB Output is correct
30 Correct 3770 ms 160740 KB Output is correct
31 Correct 3898 ms 189296 KB Output is correct
32 Correct 3924 ms 153648 KB Output is correct
33 Correct 3697 ms 140480 KB Output is correct
34 Correct 4275 ms 173884 KB Output is correct
35 Correct 4251 ms 162700 KB Output is correct
36 Correct 5159 ms 226712 KB Output is correct
37 Correct 7884 ms 336316 KB Output is correct
38 Correct 6898 ms 357200 KB Output is correct
39 Correct 5610 ms 292276 KB Output is correct
40 Correct 3768 ms 173528 KB Output is correct