| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1047107 |
2024-08-07T09:00:07 Z |
ㄷㄷ(#11083) |
Sweeping (JOI20_sweeping) |
C++17 |
|
2472 ms |
2097152 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int _N = 1500009;
int N;
vector<int> X, Y;
vector<array<int, 3>> ans;
int W[_N];
struct UF {
int P[_N];
vector<int> G[_N];
int root(int x) {
if(P[x] == x) return x;
return P[x] = root(P[x]);
}
void merg(int u, int v) {
u = root(u); v = root(v);
if(u != v) {
if(G[u].size() < G[v].size()) swap(u, v);
for(auto it: G[v]) G[u].push_back(it);
P[v] = u;
}
}
} UX, UY;
void go(vector<array<int, 3>> &V, int ox, int oy) {
if(V.empty()) return;
int d = N - ox - oy >> 1;
vector<array<int, 3>> U, R;
sort(V.begin(), V.end());
priority_queue<array<int, 2>> PX, PY;
for(auto [t, q, x]: V) if(q == 0) {
W[x] = 0;
UX.P[x] = UY.P[x] = x;
UX.G[x] = UY.G[x] = {x};
}
for(auto [t, q, x]: V) {
if(q == 0) {
if(Y[x] > oy + d) {
U.push_back({t, q, x});
W[x] = 1;
}
else if(X[x] > ox + d) {
R.push_back({t, q, x});
W[x] = 2;
}
else {
PX.push({-X[x], x});
PY.push({-Y[x], x});
}
}
if(q == 1) {
if(W[x] == 0) ans.push_back({t, X[UX.root(x)], Y[UY.root(x)]});
if(W[x] == 1) U.push_back({t, q, x});
if(W[x] == 2) R.push_back({t, q, x});
}
if(q == 2) {
if(x < oy + d) {
while(PY.size()) {
auto [v, i] = PY.top(); v = -v;
if(x < v) break;
PY.pop();
for(auto it: UY.G[i]) if(W[it] == 0) {
W[it] = 2;
R.push_back({t, 0, it});
X[it] = N - x;
Y[it] = Y[i];
}
}
R.push_back({t, q, x});
}
else {
int p = -1;
while(PX.size()) {
auto [v, i] = PX.top(); v = -v;
if(v >= N - x) break;
PX.pop();
if(p == -1) p = i;
else UX.merg(p, i);
}
if(p != -1) {
p = UX.root(p);
X[p] = N - x;
PX.push({-X[p], p});
}
if(x > oy + d) U.push_back({t, q, x});
}
}
if(q == 3) {
if(x < ox + d) {
while(PX.size()) {
auto [v, i] = PX.top(); v = -v;
if(x < v) break;
PX.pop();
for(auto it: UX.G[i]) if(W[it] == 0) {
W[it] = 1;
U.push_back({t, 0, it});
X[it] = X[i];
Y[it] = N - x;
}
}
U.push_back({t, q, x});
}
else {
int p = -1;
while(PY.size()) {
auto [v, i] = PY.top(); v = -v;
if(v >= N - x) break;
PY.pop();
if(p == -1) p = i;
else UY.merg(p, i);
}
if(p != -1) {
p = UY.root(p);
Y[p] = N - x;
PY.push({-Y[p], p});
}
if(x > ox + d) R.push_back({t, q, x});
}
}
}
go(U, ox, oy + d);
go(R, ox + d, oy);
}
int main() {
vector<array<int, 3>> V;
int M, Q; scanf("%d%d%d", &N, &M, &Q);
for(int i=0; i<M; i++) {
int x, y; scanf("%d%d", &x, &y);
V.push_back({0, 0, X.size()});
X.push_back(x); Y.push_back(y);
}
for(int i=1; i<=Q; i++) {
int t, x, y;
scanf("%d", &t);
if(t == 4) {
scanf("%d%d", &x, &y);
V.push_back({i, 0, X.size()});
X.push_back(x); Y.push_back(y);
}
else {
scanf("%d", &x);
if(t == 1) --x;
V.push_back({i, t, x});
}
}
go(V, 0, 0);
sort(ans.begin(), ans.end());
for(auto [t, x, y]: ans) printf("%d %d\n", x, y);
return 0;
}
Compilation message
sweeping.cpp: In function 'void go(std::vector<std::array<int, 3> >&, int, int)':
sweeping.cpp:30:17: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
30 | int d = N - ox - oy >> 1;
| ~~~~~~~^~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:133:28: warning: narrowing conversion of 'X.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
133 | V.push_back({0, 0, X.size()});
| ~~~~~~^~
sweeping.cpp:141:29: warning: narrowing conversion of 'X.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
141 | V.push_back({i, 0, X.size()});
| ~~~~~~^~
sweeping.cpp:130:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | int M, Q; scanf("%d%d%d", &N, &M, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:132:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | int x, y; scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
sweeping.cpp:140:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:145:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
145 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
71696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2472 ms |
229820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1649 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1649 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
71696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
