제출 #216398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216398		IOrtroiii	청소 (JOI20_sweeping)	C++14	100 / 100	7884 ms	357200 KiB

sweeping

#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 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25