oj.uz

Submission #217664

# Submission time Handle Problem Language Result Execution time Memory
217664 2020-03-30T11:46:14 Z extraterrestrial Sweeping (JOI20_sweeping) C++14
100 / 100
 5435 ms 454484 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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;
  inline void init(int n) {
    p.resize(n);
    have.resize(n);
    curval.resize(n);
    sz.resize(n);
    iota(all(p), 0);
    for (int i = 0; i < n; i++) {
      have[i] = {i};
      sz[i] = 1;
    }
  }
  int find(int v) {
    return p[v] == v ? v : p[v] = find(p[v]);
  }
  inline 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;
  }
  inline void update(int v, int x) {
    v = find(v);
    curval[v] = x;
  }
};

DSU Hx, Hy;

int n, iter;
const int N = 1e6 + 10;
pair<int, int> ans[N];
int num[2 * 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;
  Hx.init(sz);
  Hy.init(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) {
    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[comp];
              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[comp];
              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);
  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 16 ms 1624 KB Output is correct
2 Correct 10 ms 1088 KB Output is correct
3 Correct 10 ms 1496 KB Output is correct
4 Correct 14 ms 1496 KB Output is correct
5 Correct 15 ms 1624 KB Output is correct
6 Correct 7 ms 1224 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3726 ms 189216 KB Output is correct
2 Correct 3529 ms 193708 KB Output is correct
3 Correct 3624 ms 192916 KB Output is correct
4 Correct 3763 ms 284016 KB Output is correct
5 Correct 4856 ms 229036 KB Output is correct
6 Correct 4607 ms 245504 KB Output is correct
7 Correct 3583 ms 192788 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2316 ms 208012 KB Output is correct
2 Correct 2131 ms 198052 KB Output is correct
3 Correct 2476 ms 248616 KB Output is correct
4 Correct 2989 ms 354560 KB Output is correct
5 Correct 2585 ms 300480 KB Output is correct
6 Correct 2039 ms 207604 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2316 ms 208012 KB Output is correct
2 Correct 2131 ms 198052 KB Output is correct
3 Correct 2476 ms 248616 KB Output is correct
4 Correct 2989 ms 354560 KB Output is correct
5 Correct 2585 ms 300480 KB Output is correct
6 Correct 2039 ms 207604 KB Output is correct
7 Correct 2997 ms 177176 KB Output is correct
8 Correct 3022 ms 185292 KB Output is correct
9 Correct 3006 ms 171816 KB Output is correct
10 Correct 3468 ms 233268 KB Output is correct
11 Correct 3804 ms 308900 KB Output is correct
12 Correct 3478 ms 225188 KB Output is correct
13 Correct 3397 ms 396392 KB Output is correct
14 Correct 184 ms 75564 KB Output is correct
15 Correct 1640 ms 151716 KB Output is correct
16 Correct 3017 ms 185508 KB Output is correct
17 Correct 3275 ms 190916 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1624 KB Output is correct
2 Correct 10 ms 1088 KB Output is correct
3 Correct 10 ms 1496 KB Output is correct
4 Correct 14 ms 1496 KB Output is correct
5 Correct 15 ms 1624 KB Output is correct
6 Correct 7 ms 1224 KB Output is correct
7 Correct 3726 ms 189216 KB Output is correct
8 Correct 3529 ms 193708 KB Output is correct
9 Correct 3624 ms 192916 KB Output is correct
10 Correct 3763 ms 284016 KB Output is correct
11 Correct 4856 ms 229036 KB Output is correct
12 Correct 4607 ms 245504 KB Output is correct
13 Correct 3583 ms 192788 KB Output is correct
14 Correct 2316 ms 208012 KB Output is correct
15 Correct 2131 ms 198052 KB Output is correct
16 Correct 2476 ms 248616 KB Output is correct
17 Correct 2989 ms 354560 KB Output is correct
18 Correct 2585 ms 300480 KB Output is correct
19 Correct 2039 ms 207604 KB Output is correct
20 Correct 2997 ms 177176 KB Output is correct
21 Correct 3022 ms 185292 KB Output is correct
22 Correct 3006 ms 171816 KB Output is correct
23 Correct 3468 ms 233268 KB Output is correct
24 Correct 3804 ms 308900 KB Output is correct
25 Correct 3478 ms 225188 KB Output is correct
26 Correct 3397 ms 396392 KB Output is correct
27 Correct 184 ms 75564 KB Output is correct
28 Correct 1640 ms 151716 KB Output is correct
29 Correct 3017 ms 185508 KB Output is correct
30 Correct 3275 ms 190916 KB Output is correct
31 Correct 4099 ms 226412 KB Output is correct
32 Correct 3836 ms 196840 KB Output is correct
33 Correct 4202 ms 182080 KB Output is correct
34 Correct 4412 ms 233704 KB Output is correct
35 Correct 4166 ms 234764 KB Output is correct
36 Correct 4397 ms 240376 KB Output is correct
37 Correct 5435 ms 418960 KB Output is correct
38 Correct 4456 ms 454484 KB Output is correct
39 Correct 4244 ms 362760 KB Output is correct
40 Correct 3297 ms 205112 KB Output is correct