제출 #217641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
217641		extraterrestrial	청소 (JOI20_sweeping)	C++14	100 / 100	16684 ms	1404180 KiB

sweeping

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll

struct dust {
  int x, y, id;
  dust() {};
  dust(int x, int y, int id) : x(x), y(y), id(id) {};
};

struct query {
  int type, x, id;
  dust A;
  query() {};
  query(int type, int x, int id, dust A) : type(type), x(x), id(id), A(A) {};
};

struct DSU {
  vector<int> p, sz, curval;
  vector<vector<int>> have;
  DSU(int n) {
    p.resize(n);
    sz.resize(n, 1);
    have.resize(n);
    curval.resize(n);
    iota(all(p), 0);
    for (int i = 0; i < n; i++) {
      have[i] = {i};
    }
  }
  int find(int v) {
    return p[v] == v ? v : p[v] = find(p[v]);
  }
  int merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) {
      return a;
    }
    if (sz[a] < sz[b]) {
      swap(a, b);
    }
    sz[a] += sz[b];
    p[b] = a;
    for (auto it : have[b]) {
      have[a].pb(it);
    }
    return a;
  }
  void update(int v, int x) {
    v = find(v);
    curval[v] = x;
  }
};

int n, iter;
const int N = 1e6 + 10;
pair<int, int> ans[N];
void solve(vector<dust> &have, vector<query> &que, int lx, int rx, int ly, int ry) {
  if (que.empty()) {
    return;
  }
  iter++;
  int Gx = (lx + rx) / 2, Gy = (ly + ry) / 2;
  int sz = SZ(have);
  for (auto it : que) {
    if (it.type == 4) {
      sz++;
    }
  }
  if (sz == 0) {
    return;
  }
  map<int, int> lstx, lsty, num;
  DSU Hx(sz), Hy(sz);
  vector<dust> toRD, toUD;
  vector<query> toRQ, toUQ;
  int ptr = 0;
  vector<int> kl(sz);
  for (auto it : have) {
    num[it.id] = ptr;
    Hx.update(ptr, it.x);
    Hy.update(ptr, it.y);
    if (it.x > Gx) {
      toRD.pb(it);
      kl[ptr] = 1;    
    }
    else if (it.y > Gy) {
      toUD.pb(it);
      kl[ptr] = 2;
    }
    else {
      if (lstx.find(it.x) != lstx.end()) {
        lstx[it.x] = Hx.merge(ptr, lstx[it.x]);
      }
      else {
        lstx[it.x] = ptr;
      }
      if (lsty.find(it.y) != lsty.end()) {
        lsty[it.y] = Hy.merge(ptr, lsty[it.y]);
      }
      else {
        lsty[it.y] = ptr;
      }
    }
    ptr++;
  }
  for (auto it : que) {
    //cout << it.type << endl;
    if (it.type == 1) {
      if (!kl[num[it.x]]) {
        ans[it.id] = {Hx.curval[Hx.find(num[it.x])], Hy.curval[Hy.find(num[it.x])]};
      }
      else if (kl[num[it.x]] == 1) {
        toRQ.pb(it);
      }
      else {
        toUQ.pb(it);
      }
    }
    
    if (it.type == 2) {
      if (it.x > Gy) {
        toUQ.pb(it);
      }
      if (n - it.x > Gx) {
        toRQ.pb(it);
      }
      if (have.empty()) {
        continue;
      }
      
      if (n - it.x > Gx) {
        while (!lsty.empty() && lsty.begin()->F <= it.x) {
          int comp = lsty.begin()->S;
          for (auto itt : Hy.have[comp]) {
            if (!kl[itt]) {
              query cur;
              cur.type = 4;
              cur.A.x = n - it.x;
              cur.A.y = Hy.curval[Hy.find(itt)];
              cur.A.id = have[itt].id;
              toRQ.pb(cur);
              kl[itt] = 1;
            }
          }
          lsty.erase(lsty.begin());
        }
      } 
      else {
        int vl = n - it.x;
        if (lstx.begin()->F >= vl) {
          continue;
        }
        int cur = lstx.begin()->S;
        while (!lstx.empty() && lstx.begin()->F < vl) {
          cur = Hx.merge(lstx.begin()->S, cur);
          lstx.erase(lstx.begin());    
        }
        Hx.update(cur, vl);
        if (lstx.find(vl) != lstx.end()) {
          lstx[vl] = Hx.merge(lstx[vl], cur);
        }
        else {
          lstx[vl] = cur;
        }
      }
    }

    if (it.type == 3) {
      if (it.x > Gx) {
        toRQ.pb(it);
      }
      if (n - it.x > Gy) {
        toUQ.pb(it);
      }
      if (have.empty()) {
        continue;
      }
      if (n - it.x > Gy) {
        while (!lstx.empty() && lstx.begin()->F <= it.x) {
          int comp = lstx.begin()->S;
          for (auto itt : Hx.have[comp]) {
            if (!kl[itt]) {
              query cur;
              cur.type = 4;
              cur.A.id = have[itt].id;
              cur.A.x = Hx.curval[Hx.find(itt)];
              cur.A.y = n - it.x;
              toUQ.pb(cur);
              kl[itt] = 2;
            }
          }
          lstx.erase(lstx.begin());
        }
      }
      else {
        int vl = n - it.x;
        if (lsty.begin()->F >= vl) {
          continue;
        }
        int cur = lsty.begin()->S;
        while (!lsty.empty() && lsty.begin()->F < vl) {
          cur = Hy.merge(lsty.begin()->S, cur);
          lsty.erase(lsty.begin());
        }
        Hy.update(cur, vl);
        if (lsty.find(vl) != lsty.end()) {
          lsty[vl] = Hy.merge(lsty[vl], cur);
        }
        else {
          lsty[vl] = cur;
        }
      }
    }

    if (it.type == 4) {
      num[it.A.id] = SZ(have);
      Hx.update(SZ(have), it.A.x);
      Hy.update(SZ(have), it.A.y);
      have.pb(it.A);
      if (it.A.x > Gx) {
        toRQ.pb(it);
        kl[num[it.A.id]] = 1;
      }
      else if (it.A.y > Gy) {
        toUQ.pb(it);
        kl[num[it.A.id]] = 2;
      }
      else {
        if (lstx.find(it.A.x) != lstx.end()) {
          lstx[it.A.x] = Hx.merge(lstx[it.A.x], num[it.A.id]);
        }
        else {
          lstx[it.A.x] = num[it.A.id];
        }
        if (lsty.find(it.A.y) != lsty.end()) {
          lsty[it.A.y] = Hy.merge(lsty[it.A.y], num[it.A.id]);
        }
        else {
          lsty[it.A.y] = num[it.A.id];
        }
      }
    }  
  }
  solve(toRD, toRQ, Gx + 1, rx, ly, ly + (rx - Gx - 1));
  solve(toUD, toUQ, lx, lx + (ry - Gy - 1), Gy + 1, ry);
} 

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
	int m, q;
  cin >> n >> m >> q;
  vector<dust> have;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    have.pb(dust(x, y, i + 1)); 
  }
  int cnt = m;
  vector<query> que;
  for (int i = 0; i < q; i++) {
    ans[i] = {-1, -1};
    query cur;
    cur.id = i;
    cin >> cur.type;
    if (cur.type < 4) {
      cin >> cur.x;
    }
    else {
      cin >> cur.A.x >> cur.A.y;
      cur.A.id = ++cnt;
    }
    que.pb(cur);
  }
  solve(have, que, 0, n, 0, n);
  //cout << '\n';
  for (int i = 0; i < q; i++) {
    if (ans[i].F >= 0) {
      cout << ans[i].F << ' ' << ans[i].S << '\n';
    }
  }
}   

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