oj.uz

Submission #1052581

# Submission time Handle Problem Language Result Execution time Memory
1052581 2024-08-10T16:50:24 Z juicy Sweeping (JOI20_sweeping) C++17
100 / 100
 2415 ms 356764 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 80984 KB Output is correct
2 Correct 15 ms 80840 KB Output is correct
3 Correct 12 ms 81000 KB Output is correct
4 Correct 16 ms 81000 KB Output is correct
5 Correct 14 ms 80948 KB Output is correct
6 Correct 12 ms 80732 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1409 ms 234384 KB Output is correct
2 Correct 1353 ms 232612 KB Output is correct
3 Correct 1290 ms 233380 KB Output is correct
4 Correct 1119 ms 263528 KB Output is correct
5 Correct 2282 ms 239836 KB Output is correct
6 Correct 1885 ms 244952 KB Output is correct
7 Correct 1313 ms 232092 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 229024 KB Output is correct
2 Correct 1364 ms 232580 KB Output is correct
3 Correct 827 ms 249572 KB Output is correct
4 Correct 1414 ms 300192 KB Output is correct
5 Correct 1360 ms 271672 KB Output is correct
6 Correct 1249 ms 228884 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 229024 KB Output is correct
2 Correct 1364 ms 232580 KB Output is correct
3 Correct 827 ms 249572 KB Output is correct
4 Correct 1414 ms 300192 KB Output is correct
5 Correct 1360 ms 271672 KB Output is correct
6 Correct 1249 ms 228884 KB Output is correct
7 Correct 1291 ms 228772 KB Output is correct
8 Correct 1305 ms 224136 KB Output is correct
9 Correct 1314 ms 225072 KB Output is correct
10 Correct 1205 ms 246756 KB Output is correct
11 Correct 1695 ms 285728 KB Output is correct
12 Correct 2009 ms 256480 KB Output is correct
13 Correct 1796 ms 340772 KB Output is correct
14 Correct 83 ms 108104 KB Output is correct
15 Correct 347 ms 201380 KB Output is correct
16 Correct 1241 ms 226380 KB Output is correct
17 Correct 1243 ms 226288 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 80984 KB Output is correct
2 Correct 15 ms 80840 KB Output is correct
3 Correct 12 ms 81000 KB Output is correct
4 Correct 16 ms 81000 KB Output is correct
5 Correct 14 ms 80948 KB Output is correct
6 Correct 12 ms 80732 KB Output is correct
7 Correct 1409 ms 234384 KB Output is correct
8 Correct 1353 ms 232612 KB Output is correct
9 Correct 1290 ms 233380 KB Output is correct
10 Correct 1119 ms 263528 KB Output is correct
11 Correct 2282 ms 239836 KB Output is correct
12 Correct 1885 ms 244952 KB Output is correct
13 Correct 1313 ms 232092 KB Output is correct
14 Correct 1399 ms 229024 KB Output is correct
15 Correct 1364 ms 232580 KB Output is correct
16 Correct 827 ms 249572 KB Output is correct
17 Correct 1414 ms 300192 KB Output is correct
18 Correct 1360 ms 271672 KB Output is correct
19 Correct 1249 ms 228884 KB Output is correct
20 Correct 1291 ms 228772 KB Output is correct
21 Correct 1305 ms 224136 KB Output is correct
22 Correct 1314 ms 225072 KB Output is correct
23 Correct 1205 ms 246756 KB Output is correct
24 Correct 1695 ms 285728 KB Output is correct
25 Correct 2009 ms 256480 KB Output is correct
26 Correct 1796 ms 340772 KB Output is correct
27 Correct 83 ms 108104 KB Output is correct
28 Correct 347 ms 201380 KB Output is correct
29 Correct 1241 ms 226380 KB Output is correct
30 Correct 1243 ms 226288 KB Output is correct
31 Correct 1313 ms 244384 KB Output is correct
32 Correct 1353 ms 228992 KB Output is correct
33 Correct 1164 ms 231888 KB Output is correct
34 Correct 1487 ms 243684 KB Output is correct
35 Correct 1561 ms 250316 KB Output is correct
36 Correct 1179 ms 247796 KB Output is correct
37 Correct 2415 ms 356764 KB Output is correct
38 Correct 1936 ms 347600 KB Output is correct
39 Correct 1764 ms 311412 KB Output is correct
40 Correct 1278 ms 232940 KB Output is correct