QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380951 | #2434. Single Cut of Failure | ckiseki# | AC ✓ | 4726ms | 113072kb | C++20 | 4.9kb | 2024-04-07 15:28:57 | 2024-04-07 15:28:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
struct M {
int mx;
int pos;
};
M operator+(M a, M b) {
return a.mx < b.mx ? b : a;
}
const int inf = 1e9;
struct Segtree {
int n;
vector<M> st;
vector<int> lz;
Segtree(int n_) : n(n_), st(n * 2), lz(n) {
for (int i = 0; i < n; i++)
st[i + n] = {0, i};
for (int i = n - 1; i > 0; i--)
st[i] = st[i << 1] + st[i << 1 | 1];
}
void upd(int p, int v) {
st[p].mx += v;
if (p < n) lz[p] += v;
}
void pull(int p) {
while (p >>= 1) {
st[p] = st[p << 1] + st[p << 1 | 1];
st[p].mx += lz[p];
}
}
void push(int p) {
for (int h = __lg(n); h >= 0; h--) {
int i = p >> h;
if (i <= 1) continue;
upd(i, lz[i >> 1]);
upd(i ^ 1, lz[i >> 1]);
lz[i >> 1] = 0;
}
}
void add(int l, int r, int v) {
if (l >= r) return;
assert(l < n && r <= n);
int tl = l, tr = r;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) upd(l++, v);
if (r & 1) upd(--r, v);
}
pull(tl + n), pull(tr - 1 + n);
}
M query(int l, int r) {
assert(l < r);
push(l + n), push(r - 1 + n);
M res = {-inf, -inf};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = res + st[l++];
if (r & 1) res = res + st[--r];
}
return res;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cout.precision(20);
cout << fixed;
int n, w, h;
cin >> n >> w >> h;
auto mapping = [&](int x, int y) {
if (y == 0) {
return x;
} else if (x == w) {
return w + y;
} else if (y == h) {
return w + h + (w - x);
} else {
return w + h + w + (h - y);
}
};
const int C = w + h + w + h;
vector<int> u;
vector<tuple<int,int,int,int>> evt;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int l = mapping(x1, y1);
int r = mapping(x2, y2);
u.push_back(l);
u.push_back(r);
if (l > r)
swap(l, r);
assert(l < r);
// rng[i] = {l, r};
evt.emplace_back(0, 1, l, r);
evt.emplace_back(l, -2, l, r);
evt.emplace_back(r, 2, l, r);
evt.emplace_back(C, -1, l, r);
}
const int corner[5] = {
mapping(0, 0),
mapping(w, 0),
mapping(w, h),
mapping(0, h),
C
};
for (int i = 0; i < 4; i++)
evt.emplace_back(corner[i], 0, i, 0);
ranges::sort(evt);
for (int j = 0; j < 5; j++)
u.push_back(corner[j]);
ranges::sort(u);
int ucorner[5] = {};
for (int j = 0; j < 5; j++)
ucorner[j] = lower_bound(all(u), corner[j]) - u.begin();
Segtree sgt(u.size());
orange(all(u));
int global = 0;
int current_side = -1;
for (size_t i = 0, j; i < evt.size(); i = j) {
for (j = i; j < evt.size(); j++) {
if (get<0>(evt[j]) != get<0>(evt[i])) break;
auto [_, tp, l, r] = evt[j];
if (tp != 0) {
l = lower_bound(all(u), l) - u.begin();
r = lower_bound(all(u), r) - u.begin();
debug(l, r);
sgt.add(l, r, tp);
} else {
current_side = l;
}
if (abs(tp) == 2) {
if (tp < 0) {
global += 1;
} else {
global -= 1;
}
}
}
auto unmapping = [&](long double z) -> pair<long double, long double> {
if (z <= w) {
return {z, 0};
} else if (z <= w + h) {
return {w, z - w};
} else if (z <= w + h + w) {
return {w - (z - w - h), h};
} else {
return {0, h - (z - w - h - w)};
}
};
for (int t = 0; t < 4; t++) {
if (t == current_side) continue;
int l = ucorner[t];
int r = ucorner[t + 1];
auto R = sgt.query(l, r);
R.mx += global;
assert(R.mx >= 0 && R.mx <= n);
if (R.mx == n) {
long double a = (get<0>(evt[i]) + get<0>(evt[j])) / 2.0;
long double b;
if (R.pos + 1 == u.size()) {
b = (u[0] + u[1]) / 2.0;
} else {
b = (u[R.pos] + u[R.pos + 1]) / 2.0;
}
auto [ax, ay] = unmapping(a);
auto [bx, by] = unmapping(b);
cout << 1 << '\n';
cout << ax << ' ' << ay << ' ' << bx << ' ' << by << '\n';
return 0;
}
}
}
cout << 2 << '\n';
cout << 0.5 << ' ' << 0 << ' ' << w - 0.5 << ' ' << h << '\n';
cout << 0.5 << ' ' << h << ' ' << w - 0.5 << ' ' << 0 << '\n';
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 3896kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3848kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3968kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3996kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3924kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 3836kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3864kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 3960kb
Test #9:
score: 0
Accepted
time: 271ms
memory: 31148kb
Test #10:
score: 0
Accepted
time: 269ms
memory: 30524kb
Test #11:
score: 0
Accepted
time: 264ms
memory: 30588kb
Test #12:
score: 0
Accepted
time: 379ms
memory: 30944kb
Test #13:
score: 0
Accepted
time: 274ms
memory: 30612kb
Test #14:
score: 0
Accepted
time: 760ms
memory: 31256kb
Test #15:
score: 0
Accepted
time: 773ms
memory: 30508kb
Test #16:
score: 0
Accepted
time: 270ms
memory: 30968kb
Test #17:
score: 0
Accepted
time: 799ms
memory: 30552kb
Test #18:
score: 0
Accepted
time: 272ms
memory: 30524kb
Test #19:
score: 0
Accepted
time: 796ms
memory: 30824kb
Test #20:
score: 0
Accepted
time: 372ms
memory: 30704kb
Test #21:
score: 0
Accepted
time: 796ms
memory: 30576kb
Test #22:
score: 0
Accepted
time: 266ms
memory: 30688kb
Test #23:
score: 0
Accepted
time: 329ms
memory: 30652kb
Test #24:
score: 0
Accepted
time: 1995ms
memory: 113020kb
Test #25:
score: 0
Accepted
time: 4358ms
memory: 112912kb
Test #26:
score: 0
Accepted
time: 1ms
memory: 3828kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 3868kb
Test #28:
score: 0
Accepted
time: 1ms
memory: 3928kb
Test #29:
score: 0
Accepted
time: 9ms
memory: 4092kb
Test #30:
score: 0
Accepted
time: 80ms
memory: 6412kb
Test #31:
score: 0
Accepted
time: 3949ms
memory: 99360kb
Test #32:
score: 0
Accepted
time: 4726ms
memory: 112988kb
Test #33:
score: 0
Accepted
time: 1ms
memory: 3884kb
Test #34:
score: 0
Accepted
time: 1ms
memory: 3844kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 4056kb
Test #36:
score: 0
Accepted
time: 11ms
memory: 4332kb
Test #37:
score: 0
Accepted
time: 32ms
memory: 6468kb
Test #38:
score: 0
Accepted
time: 298ms
memory: 23900kb
Test #39:
score: 0
Accepted
time: 1631ms
memory: 112928kb
Test #40:
score: 0
Accepted
time: 1ms
memory: 4068kb
Test #41:
score: 0
Accepted
time: 1ms
memory: 3860kb
Test #42:
score: 0
Accepted
time: 1ms
memory: 3888kb
Test #43:
score: 0
Accepted
time: 20ms
memory: 4180kb
Test #44:
score: 0
Accepted
time: 242ms
memory: 14048kb
Test #45:
score: 0
Accepted
time: 2789ms
memory: 81892kb
Test #46:
score: 0
Accepted
time: 4459ms
memory: 113072kb
Test #47:
score: 0
Accepted
time: 1ms
memory: 3964kb
Test #48:
score: 0
Accepted
time: 1ms
memory: 3964kb
Test #49:
score: 0
Accepted
time: 0ms
memory: 3864kb
Test #50:
score: 0
Accepted
time: 0ms
memory: 3780kb
Test #51:
score: 0
Accepted
time: 0ms
memory: 3832kb
Test #52:
score: 0
Accepted
time: 1ms
memory: 3828kb
Test #53:
score: 0
Accepted
time: 0ms
memory: 3928kb
Test #54:
score: 0
Accepted
time: 0ms
memory: 3844kb
Test #55:
score: 0
Accepted
time: 1ms
memory: 3844kb
Test #56:
score: 0
Accepted
time: 0ms
memory: 3888kb
Test #57:
score: 0
Accepted
time: 0ms
memory: 3832kb
Test #58:
score: 0
Accepted
time: 0ms
memory: 3944kb
Test #59:
score: 0
Accepted
time: 0ms
memory: 3824kb
Test #60:
score: 0
Accepted
time: 0ms
memory: 3828kb
Test #61:
score: 0
Accepted
time: 0ms
memory: 3772kb
Test #62:
score: 0
Accepted
time: 0ms
memory: 3924kb
Test #63:
score: 0
Accepted
time: 0ms
memory: 3792kb
Test #64:
score: 0
Accepted
time: 0ms
memory: 3960kb
Test #65:
score: 0
Accepted
time: 1ms
memory: 3828kb
Test #66:
score: 0
Accepted
time: 0ms
memory: 3892kb
Test #67:
score: 0
Accepted
time: 0ms
memory: 3836kb
Test #68:
score: 0
Accepted
time: 1ms
memory: 3776kb
Test #69:
score: 0
Accepted
time: 0ms
memory: 3828kb
Test #70:
score: 0
Accepted
time: 1ms
memory: 3824kb
Test #71:
score: 0
Accepted
time: 78ms
memory: 14528kb
Test #72:
score: 0
Accepted
time: 78ms
memory: 15144kb
Test #73:
score: 0
Accepted
time: 95ms
memory: 14240kb
Test #74:
score: 0
Accepted
time: 287ms
memory: 16120kb
Test #75:
score: 0
Accepted
time: 83ms
memory: 14376kb
Test #76:
score: 0
Accepted
time: 1ms
memory: 3928kb