oj.uz

Submission #217641

# Submission time Handle Problem Language Result Execution time Memory
217641 2020-03-30T11:33:40 Z extraterrestrial Sweeping (JOI20_sweeping) C++14
100 / 100
 16684 ms 1404180 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2628 KB Output is correct
2 Correct 15 ms 1344 KB Output is correct
3 Correct 16 ms 2008 KB Output is correct
4 Correct 32 ms 2500 KB Output is correct
5 Correct 24 ms 2796 KB Output is correct
6 Correct 9 ms 1480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9759 ms 351816 KB Output is correct
2 Correct 9771 ms 354040 KB Output is correct
3 Correct 9356 ms 353536 KB Output is correct
4 Correct 11893 ms 585492 KB Output is correct
5 Correct 12307 ms 480536 KB Output is correct
6 Correct 12691 ms 469932 KB Output is correct
7 Correct 9278 ms 348052 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7842 ms 410848 KB Output is correct
2 Correct 7922 ms 431292 KB Output is correct
3 Correct 7848 ms 517548 KB Output is correct
4 Correct 8643 ms 1167284 KB Output is correct
5 Correct 9653 ms 713288 KB Output is correct
6 Correct 8972 ms 426812 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 7842 ms 410848 KB Output is correct
2 Correct 7922 ms 431292 KB Output is correct
3 Correct 7848 ms 517548 KB Output is correct
4 Correct 8643 ms 1167284 KB Output is correct
5 Correct 9653 ms 713288 KB Output is correct
6 Correct 8972 ms 426812 KB Output is correct
7 Correct 9138 ms 376972 KB Output is correct
8 Correct 9338 ms 400624 KB Output is correct
9 Correct 8537 ms 352252 KB Output is correct
10 Correct 11079 ms 491640 KB Output is correct
11 Correct 11774 ms 963096 KB Output is correct
12 Correct 12957 ms 531992 KB Output is correct
13 Correct 14360 ms 1078352 KB Output is correct
14 Correct 184 ms 75436 KB Output is correct
15 Correct 3827 ms 221296 KB Output is correct
16 Correct 8347 ms 398116 KB Output is correct
17 Correct 8587 ms 420116 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2628 KB Output is correct
2 Correct 15 ms 1344 KB Output is correct
3 Correct 16 ms 2008 KB Output is correct
4 Correct 32 ms 2500 KB Output is correct
5 Correct 24 ms 2796 KB Output is correct
6 Correct 9 ms 1480 KB Output is correct
7 Correct 9759 ms 351816 KB Output is correct
8 Correct 9771 ms 354040 KB Output is correct
9 Correct 9356 ms 353536 KB Output is correct
10 Correct 11893 ms 585492 KB Output is correct
11 Correct 12307 ms 480536 KB Output is correct
12 Correct 12691 ms 469932 KB Output is correct
13 Correct 9278 ms 348052 KB Output is correct
14 Correct 7842 ms 410848 KB Output is correct
15 Correct 7922 ms 431292 KB Output is correct
16 Correct 7848 ms 517548 KB Output is correct
17 Correct 8643 ms 1167284 KB Output is correct
18 Correct 9653 ms 713288 KB Output is correct
19 Correct 8972 ms 426812 KB Output is correct
20 Correct 9138 ms 376972 KB Output is correct
21 Correct 9338 ms 400624 KB Output is correct
22 Correct 8537 ms 352252 KB Output is correct
23 Correct 11079 ms 491640 KB Output is correct
24 Correct 11774 ms 963096 KB Output is correct
25 Correct 12957 ms 531992 KB Output is correct
26 Correct 14360 ms 1078352 KB Output is correct
27 Correct 184 ms 75436 KB Output is correct
28 Correct 3827 ms 221296 KB Output is correct
29 Correct 8347 ms 398116 KB Output is correct
30 Correct 8587 ms 420116 KB Output is correct
31 Correct 10398 ms 546872 KB Output is correct
32 Correct 9219 ms 386536 KB Output is correct
33 Correct 10336 ms 327560 KB Output is correct
34 Correct 10407 ms 541724 KB Output is correct
35 Correct 10689 ms 467220 KB Output is correct
36 Correct 11777 ms 525324 KB Output is correct
37 Correct 14910 ms 1404180 KB Output is correct
38 Correct 16684 ms 1266788 KB Output is correct
39 Correct 14034 ms 1003932 KB Output is correct
40 Correct 9632 ms 479348 KB Output is correct