Submission #1052581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052581		juicy	Sweeping (JOI20_sweeping)	C++17	100 / 100	2415 ms	356764 KiB

sweeping

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 15e5 + 5;

int value[2 * N], lab[2 * N], side[N];
vector<int> comp[2 * N];
array<int, 2> pt[N], res[N];

int find(int u) {
  return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void mrg(int u, int v) {
  if ((u = find(u)) == (v = find(v))) {
    return;
  }
  if (lab[u] > lab[v]) {
    swap(u, v);
  }
  lab[u] += lab[v]; 
  lab[v] = u;
  comp[u].insert(comp[u].end(), comp[v].begin(), comp[v].end());
  vector<int>().swap(comp[v]);
}

void dc(int l, int r, vector<array<int, 3>> &events) {
  if (!events.size() || l > r) {
    return;
  }
  priority_queue<array<int, 2>> ma;
  priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> mi;
  int md = (l + r) / 2;
  vector<array<int, 3>> lt, rt;
  for (auto [t, x, id] : events) {
    if (id) {
      if (side[x] == -1) {
        lt.push_back({t, x, id});
      } else if (side[x] == 1) {
        rt.push_back({t, x, id});
      } else {
        res[id] = {value[find(x * 2)], value[find(x * 2 + 1)]};
      }
    } else if (t == 0) {
      if (pt[x][0] <= md && md <= pt[x][1]) {
        side[x] = 0;
        for (int it = 0; it < 2; ++it) {
          int u = x * 2 + it;
          lab[u] = -1;
          vector<int>().swap(comp[u]);
          comp[u].push_back(x);
          value[u] = pt[x][it];
        }
        mi.push({value[x * 2], x * 2});
        ma.push({value[x * 2 + 1], x * 2 + 1});
      } else if (pt[x][1] < md) {
        lt.push_back({t, x, id});
        side[x] = -1;
      } else {
        rt.push_back({t, x, id});
        side[x] = 1;
      }
    } else if (t == 2) {
      if (x <= md) {
        int pr = -1;
        while (mi.size() && mi.top()[0] <= x) {
          auto [c, u] = mi.top(); mi.pop();
          if (pr == -1) {
            pr = u;
          } else {
            mrg(pr, u);
          }
        }
        if (~pr) {
          pr = find(pr);
          value[pr] = x;
          mi.push({value[pr], pr});
        }
        if (x < md) {
          lt.push_back({t, x, id});
        }
      } else {
        rt.push_back({t, x, id});
        while (ma.size() && ma.top()[0] >= x) {
          auto [c, u] = ma.top(); ma.pop();
          for (auto v : comp[u]) {
            if (side[v] == 0) {
              side[v] = 1;
              pt[v][0] = x, pt[v][1] = c;
              rt.push_back({0, v, 0});
            }
          }
          vector<int>().swap(comp[u]);
        }
      }
    } else {
      if (x >= md) {
        int pr = -1;
        while (ma.size() && ma.top()[0] >= x) {
          auto [c, u] = ma.top(); ma.pop();
          if (pr == -1) {
            pr = u;
          } else {
            mrg(pr, u);
          }
        }
        if (~pr) {
          pr = find(pr);
          value[pr] = x;
          ma.push({value[pr], pr});
        }
        if (x > md) {
          rt.push_back({t, x, id});
        }
      } else {
        lt.push_back({t, x, id});
        while (mi.size() && mi.top()[0] <= x) {
          auto [c, u] = mi.top(); mi.pop();
          for (auto v : comp[u]) {
            if (side[v] == 0) {
              pt[v][0] = c, pt[v][1] = x;
              side[v] = -1;
              lt.push_back({0, v, 0});
            }
          }
          vector<int>().swap(comp[u]);
        }
      }
    }
  }
  dc(l, md - 1, lt);
  dc(md + 1, r, rt);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  
  int n, m, q;
  cin >> n >> m >> q;
  vector<array<int, 3>> events;
  int p = 0;
  while (m--) {
    int x, y; cin >> x >> y; y = n - y;
    pt[++p] = {x, y};
    events.push_back({0, p, 0});
  }  
  int k = 0;
  while (q--) {
    int type; cin >> type;
    if (type == 1) {
      int x; cin >> x;
      events.push_back({1, x, ++k});
    } else if (type == 4) {
      int a, b; cin >> a >> b; b = n - b;
      pt[++p] = {a, b};
      events.push_back({0, p, 0});
    } else {
      int l; cin >> l;
      if (type == 2) {
        events.push_back({2, n - l, 0});
      } else {
        events.push_back({3, l, 0});
      }
    }
  }
  dc(1, n, events);
  for (int i = 1; i <= k; ++i) {
    cout << res[i][0] << " " << n - res[i][1] << "\n";
  }
  return 0;
}

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