QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179917 | #7224. The Imaginary Girlfriend | ucup-team004 | ML | 2708ms | 521072kb | C++20 | 8.7kb | 2023-09-15 13:27:09 | 2023-09-15 13:27:10 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> x1(n), y1(n), x2(n), y2(n);
std::vector<int> vx, vy;
vx.reserve(2 * n + 2);
vy.reserve(2 * n + 2);
for (int i = 0; i < n; i++) {
std::cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
vx.push_back(x1[i]);
vy.push_back(y1[i]);
vx.push_back(x2[i]);
vy.push_back(y2[i]);
}
int sx, sy, tx, ty;
std::cin >> sx >> sy >> tx >> ty;
vx.push_back(sx);
vy.push_back(sy);
vx.push_back(tx);
vy.push_back(ty);
if (sx == tx && sy == ty) {
std::cout << 0 << "\n";
return 0;
}
std::sort(vx.begin(), vx.end());
std::sort(vy.begin(), vy.end());
vx.erase(std::unique(vx.begin(), vx.end()), vx.end());
vy.erase(std::unique(vy.begin(), vy.end()), vy.end());
const int nx = vx.size();
const int ny = vy.size();
for (int i = 0; i < n; i++) {
x1[i] = std::lower_bound(vx.begin(), vx.end(), x1[i]) - vx.begin();
y1[i] = std::lower_bound(vy.begin(), vy.end(), y1[i]) - vy.begin();
x2[i] = std::lower_bound(vx.begin(), vx.end(), x2[i]) - vx.begin();
y2[i] = std::lower_bound(vy.begin(), vy.end(), y2[i]) - vy.begin();
}
sx = std::lower_bound(vx.begin(), vx.end(), sx) - vx.begin();
sy = std::lower_bound(vy.begin(), vy.end(), sy) - vy.begin();
tx = std::lower_bound(vx.begin(), vx.end(), tx) - vx.begin();
ty = std::lower_bound(vy.begin(), vy.end(), ty) - vy.begin();
std::map<std::array<int, 2>, int> id;
std::vector<std::array<int, 2>> ver;
std::vector<std::vector<int>> px(nx), py(ny);
std::vector<std::vector<std::array<int, 2>>> segx(nx), segy(ny);
for (int i = 0; i < n; i++) {
if (x1[i] == x2[i]) {
if (y1[i] > y2[i]) {
std::swap(y1[i], y2[i]);
}
segx[x1[i]].push_back({y1[i], y2[i]});
} else {
if (x1[i] > x2[i]) {
std::swap(x1[i], x2[i]);
}
segy[y1[i]].push_back({x1[i], x2[i]});
}
}
for (int x = 0; x < nx; x++) {
std::sort(segx[x].begin(), segx[x].end());
}
for (int y = 0; y < ny; y++) {
std::sort(segy[y].begin(), segy[y].end());
}
auto find = [&](auto &a, int x) {
auto it = std::lower_bound(a.begin(), a.end(), std::array{x + 1, 0});
if (it == a.begin()) {
return false;
}
it--;
return (*it)[1] >= x;
};
auto add = [&](int x, int y) {
if (id.count({x, y})) {
return;
}
if (!find(segx[x], y) && !find(segy[y], x)) {
return;
}
int u = id[{x, y}] = ver.size();
ver.push_back({x, y});
px[x].push_back(u);
py[y].push_back(u);
};
std::vector<int> dx{0, nx - 1};
constexpr int B = 200;
for (int i = B; i < nx; i += B) {
dx.push_back(i);
}
dx.push_back(sx);
dx.push_back(tx);
std::sort(dx.begin(), dx.end());
dx.erase(std::unique(dx.begin(), dx.end()), dx.end());
for (auto x : dx) {
for (int y = 0; y < ny; y++) {
add(x, y);
}
}
for (int i = 0; i + 1 < dx.size(); i++) {
int xl = dx[i], xr = dx[i + 1];
std::vector<int> ys;
bool first = true;
for (int y = 0; y < ny; y++) {
for (auto [l, r] : segy[y]) {
if (r < xl || l > xr) {
continue;
}
if (l <= xl && r >= xr) {
ys.push_back(y);
if (first) {
for (int x = xl; x <= xr; x++) {
add(x, y);
}
first = false;
}
} else {
for (int x = xl; x <= xr; x++) {
add(x, y);
}
if (!ys.empty()) {
for (int x = xl; x <= xr; x++) {
add(x, ys.back());
}
}
first = true;
}
}
}
if (!ys.empty()) {
for (int x = xl; x <= xr; x++) {
add(x, ys.back());
}
}
std::set<int> h;
for (auto y : ys) {
h.insert(y);
}
for (int x = xl + 1; x < xr; x++) {
for (auto [l, r] : segx[x]) {
int j = std::lower_bound(ys.begin(), ys.end(), l) - ys.begin();
int k = std::lower_bound(ys.begin(), ys.end(), r + 1) - ys.begin() - 1;
if (j > k) {
continue;
}
l = ys[j];
r = ys[k];
add(x, l);
add(x, r);
auto it = h.lower_bound(l);
while (it != h.end() && *it <= r) {
add(x, *it);
it = h.erase(it);
}
h.insert(l);
h.insert(r);
}
}
for (auto y : ys) {
h.insert(y);
}
for (int x = xr - 1; x > xl; x--) {
for (auto [l, r] : segx[x]) {
int j = std::lower_bound(ys.begin(), ys.end(), l) - ys.begin();
int k = std::lower_bound(ys.begin(), ys.end(), r + 1) - ys.begin() - 1;
if (j > k) {
continue;
}
l = ys[j];
r = ys[k];
add(x, l);
add(x, r);
auto it = h.lower_bound(l);
while (it != h.end() && *it <= r) {
add(x, *it);
it = h.erase(it);
}
h.insert(l);
h.insert(r);
}
}
}
for (int i = 0; i < n; i++) {
add(x1[i], y1[i]);
add(x2[i], y2[i]);
}
add(sx, sy);
add(tx, ty);
const int V = ver.size();
std::vector<std::array<int, 4>> adj(V);
std::vector<int> cnt(V);
std::vector<i64> dis(V, -1);
auto addEdge = [&](int u, int v) {
adj[u][cnt[u]++] = v;
adj[v][cnt[v]++] = u;
};
for (int x = 0; x < nx; x++) {
int m = px[x].size();
std::sort(px[x].begin(), px[x].end(),
[&](int i, int j) {
return ver[i][1] < ver[j][1];
});
for (int i = 0, j = 0; auto [l, r] : segx[x]) {
while (i < m && ver[px[x][i]][1] < l) {
i++;
}
while (j < m && ver[px[x][j]][1] <= r) {
j++;
}
for (int k = i; k < j - 1; k++) {
int u = px[x][k];
int v = px[x][k + 1];
addEdge(u, v);
}
}
}
for (int y = 0; y < ny; y++) {
int m = py[y].size();
std::sort(py[y].begin(), py[y].end(),
[&](int i, int j) {
return ver[i][0] < ver[j][0];
});
for (int i = 0, j = 0; auto [l, r] : segy[y]) {
while (i < m && ver[py[y][i]][0] < l) {
i++;
}
while (j < m && ver[py[y][j]][0] <= r) {
j++;
}
for (int k = i; k < j - 1; k++) {
int u = py[y][k];
int v = py[y][k + 1];
addEdge(u, v);
}
}
}
if (!id.count({sx, sy})) {
std::cout << -1 << "\n";
return 0;
}
if (!id.count({tx, ty})) {
std::cout << -1 << "\n";
return 0;
}
int S = id[{sx, sy}];
int T = id[{tx, ty}];
std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> q;
q.emplace(0, S);
dis[S] = 0;
while (!q.empty()) {
auto [d, x] = q.top();
q.pop();
if (dis[x] < d) {
continue;
}
for (int i = 0; i < cnt[x]; i++) {
int y = adj[x][i];
int w = std::abs(vx[ver[x][0]] - vx[ver[y][0]]) + std::abs(vy[ver[x][1]] - vy[ver[y][1]]);
if (dis[y] == -1 || dis[y] > d + w) {
dis[y] = d + w;
q.emplace(d + w, y);
}
}
}
std::cout << dis[T] << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
8 0 0 0 2 0 2 2 2 2 2 2 0 2 0 0 0 -1 1 1 1 1 1 1 3 1 3 -1 3 -1 1 -1 3 2 0 -1 3
output:
6
result:
ok answer is '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
10 0 0 0 3 1 0 1 3 2 0 2 3 3 0 3 3 0 0 3 0 -1 1 4 1 -1 1 -1 10000 4 1 4 10000 -1000 10000 1000 10000 0 10000 0 5000 2 3 0 5000
output:
15005
result:
ok answer is '15005'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
19 -100000 0 100000 0 -100000 0 -100000 100000 100000 0 100000 100000 -100000 100000 100000 100000 10000 0 10000 10 -10000 0 -10000 10 10000 10 -10000 10 -10000 100000 -10000 99999 -10000 99999 -10001 99999 -10001 99999 -10001 99998 -10001 99998 -10002 99998 -10002 99998 -10002 99997 -10002 99997 -1...
output:
300015
result:
ok answer is '300015'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
19 -100000 0 100000 0 -100000 0 -100000 100000 100000 0 100000 100000 -100000 100000 100000 100000 10000 0 10000 10 -10000 0 -10000 10 10000 10 -10000 10 -10000 100000 -10000 99999 -10000 99999 -10001 99999 -10001 99999 -10001 99998 -10001 99998 -10002 99998 -10002 99998 -10002 99997 -10002 99997 -1...
output:
300015
result:
ok answer is '300015'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3572kb
input:
200 0 0 99 0 0 1 99 1 0 2 99 2 0 3 99 3 0 4 99 4 0 5 99 5 0 6 99 6 0 7 99 7 0 8 99 8 0 9 99 9 0 10 99 10 0 11 99 11 0 12 99 12 0 13 99 13 0 14 99 14 0 15 99 15 0 16 99 16 0 17 99 17 0 18 99 18 0 19 99 19 0 20 99 20 0 21 99 21 0 22 99 22 0 23 99 23 0 24 99 24 0 25 99 25 0 26 99 26 0 27 99 27 0 28 99 ...
output:
198
result:
ok answer is '198'
Test #6:
score: 0
Accepted
time: 6ms
memory: 5416kb
input:
2000 0 0 999 0 0 1 999 1 0 2 999 2 0 3 999 3 0 4 999 4 0 5 999 5 0 6 999 6 0 7 999 7 0 8 999 8 0 9 999 9 0 10 999 10 0 11 999 11 0 12 999 12 0 13 999 13 0 14 999 14 0 15 999 15 0 16 999 16 0 17 999 17 0 18 999 18 0 19 999 19 0 20 999 20 0 21 999 21 0 22 999 22 0 23 999 23 0 24 999 24 0 25 999 25 0 2...
output:
1998
result:
ok answer is '1998'
Test #7:
score: 0
Accepted
time: 24ms
memory: 10896kb
input:
4000 0 0 1999 0 0 1 1999 1 0 2 1999 2 0 3 1999 3 0 4 1999 4 0 5 1999 5 0 6 1999 6 0 7 1999 7 0 8 1999 8 0 9 1999 9 0 10 1999 10 0 11 1999 11 0 12 1999 12 0 13 1999 13 0 14 1999 14 0 15 1999 15 0 16 1999 16 0 17 1999 17 0 18 1999 18 0 19 1999 19 0 20 1999 20 0 21 1999 21 0 22 1999 22 0 23 1999 23 0 2...
output:
3998
result:
ok answer is '3998'
Test #8:
score: 0
Accepted
time: 45ms
memory: 20000kb
input:
6000 0 0 2999 0 0 1 2999 1 0 2 2999 2 0 3 2999 3 0 4 2999 4 0 5 2999 5 0 6 2999 6 0 7 2999 7 0 8 2999 8 0 9 2999 9 0 10 2999 10 0 11 2999 11 0 12 2999 12 0 13 2999 13 0 14 2999 14 0 15 2999 15 0 16 2999 16 0 17 2999 17 0 18 2999 18 0 19 2999 19 0 20 2999 20 0 21 2999 21 0 22 2999 22 0 23 2999 23 0 2...
output:
5998
result:
ok answer is '5998'
Test #9:
score: 0
Accepted
time: 107ms
memory: 31268kb
input:
8000 0 0 3999 0 0 1 3999 1 0 2 3999 2 0 3 3999 3 0 4 3999 4 0 5 3999 5 0 6 3999 6 0 7 3999 7 0 8 3999 8 0 9 3999 9 0 10 3999 10 0 11 3999 11 0 12 3999 12 0 13 3999 13 0 14 3999 14 0 15 3999 15 0 16 3999 16 0 17 3999 17 0 18 3999 18 0 19 3999 19 0 20 3999 20 0 21 3999 21 0 22 3999 22 0 23 3999 23 0 2...
output:
3999
result:
ok answer is '3999'
Test #10:
score: 0
Accepted
time: 171ms
memory: 48532kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
6000
result:
ok answer is '6000'
Test #11:
score: 0
Accepted
time: 439ms
memory: 157316kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
-1
result:
ok answer is '-1'
Test #12:
score: 0
Accepted
time: 163ms
memory: 47644kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
9998
result:
ok answer is '9998'
Test #13:
score: 0
Accepted
time: 166ms
memory: 48172kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
1
result:
ok answer is '1'
Test #14:
score: 0
Accepted
time: 169ms
memory: 48192kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
6999
result:
ok answer is '6999'
Test #15:
score: 0
Accepted
time: 175ms
memory: 50052kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
3444
result:
ok answer is '3444'
Test #16:
score: 0
Accepted
time: 1021ms
memory: 212700kb
input:
10000 0 -100000 0 23596 8 0 8 21816 18 0 18 21647 32 0 32 22755 51 0 51 24090 62 0 62 25762 75 0 75 25690 80 0 80 25172 99 0 99 22701 103 0 103 24465 113 0 113 24377 114 0 114 23874 120 0 120 21658 133 0 133 23998 136 0 136 24655 144 0 144 24588 148 0 148 26353 156 0 156 24989 166 0 166 23284 167 0 ...
output:
-1
result:
ok answer is '-1'
Test #17:
score: 0
Accepted
time: 975ms
memory: 203048kb
input:
10000 0 -100000 0 23596 8 0 8 21816 18 0 18 21647 32 0 32 22755 51 0 51 24090 62 0 62 25762 75 0 75 25690 80 0 80 25172 99 0 99 22701 103 0 103 24465 113 0 113 24377 114 0 114 23874 120 0 120 21658 133 0 133 23998 136 0 136 24655 144 0 144 24588 148 0 148 26353 156 0 156 24989 166 0 166 23284 167 0 ...
output:
252902
result:
ok answer is '252902'
Test #18:
score: 0
Accepted
time: 2677ms
memory: 496036kb
input:
10000 8158 -4495 7837 -4495 -397 -7478 -397 3130 7504 -2577 7504 -2652 2013 6377 755 6377 5949 1604 -9102 1604 -8471 -1528 -8471 5990 1902 9408 1902 -9198 -5953 3495 -5953 -4620 5657 9430 1881 9430 7889 3790 6082 3790 6509 -9526 6509 3953 -6704 -5019 -6704 4280 -5162 -3352 8454 -3352 2869 -3295 -975...
output:
1184
result:
ok answer is '1184'
Test #19:
score: 0
Accepted
time: 2523ms
memory: 472632kb
input:
10000 -4313 3855 -4313 3686 -4969 1015 -4969 -1445 -4629 -1420 -4629 472 1158 -653 -3577 -653 -1466 3829 -1899 3829 -1520 -4970 -1520 4574 -3999 1710 -3999 4256 -1202 -3153 3673 -3153 -3695 -4901 -3695 1258 -887 4460 -887 -1031 2638 1886 2638 2672 -2650 2664 -2410 2664 -2996 3096 2784 3096 744 -2078...
output:
7111
result:
ok answer is '7111'
Test #20:
score: 0
Accepted
time: 2422ms
memory: 428976kb
input:
10000 -2170 -2277 -1952 -2277 -364 -994 1373 -994 119 -1954 1785 -1954 -479 207 2445 207 -632 -176 -632 1635 -2436 2061 -2436 -1026 -1952 -1488 1962 -1488 74 1043 74 -1235 -1744 -2496 -1744 753 2319 778 2319 -2466 684 -397 684 944 2229 596 55 596 1078 -1590 1078 1012 -2259 -2072 -756 -2072 -504 -213...
output:
2140
result:
ok answer is '2140'
Test #21:
score: 0
Accepted
time: 2708ms
memory: 521072kb
input:
10000 5328 -2368 5328 11391 -15488 10013 -15488 -13741 16204 19463 16204 12899 8265 -3665 8265 6603 -3143 7482 -13860 7482 -18868 1229 -18868 5104 -5996 -3301 4384 -3301 -2169 -16062 -7948 -16062 -4676 -1245 -4676 -9882 -18363 -6529 -10350 -6529 10209 -2545 10209 15131 4254 -11754 4254 -18196 -3293 ...
output:
29574
result:
ok answer is '29574'
Test #22:
score: 0
Accepted
time: 2630ms
memory: 513236kb
input:
10000 -39351 7530 -44337 7530 -43729 -1623 -43729 19394 13752 42528 20478 42528 -29579 41446 -43975 41446 49902 -39939 -2218 -39939 -16459 39580 -16459 24843 9615 -18132 -29115 -18132 33291 8655 -28634 8655 39567 6038 -19491 6038 47795 -23496 -20844 -23496 -30598 13531 -30598 -13406 -49557 27474 -49...
output:
59489
result:
ok answer is '59489'
Test #23:
score: -100
Memory Limit Exceeded
input:
10000 -85664 -61700 -85664 99867 95422 20038 95422 18057 91898 -40486 14927 -40486 38244 31860 99359 31860 -59775 42827 -73804 42827 48339 -33447 92130 -33447 -13971 66025 -13971 65659 7688 -96927 -77186 -96927 -43896 -39072 -35882 -39072 -97402 89214 -15350 89214 28861 73359 28861 92069 1987 -97392...