QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#179924 | #7224. The Imaginary Girlfriend | ucup-team004 | AC ✓ | 1535ms | 336020kb | C++20 | 8.9kb | 2023-09-15 13:32:29 | 2023-09-15 13:32:30 |
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(n + 2);
vy.reserve(n + 2);
for (int i = 0; i < n; i++) {
std::cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
if (x1[i] == x2[i]) {
vx.push_back(x1[i]);
} else {
vy.push_back(y1[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++) {
if (x1[i] > x2[i]) {
std::swap(x1[i], x2[i]);
}
if (y1[i] > y2[i]) {
std::swap(y1[i], y2[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] + 1) - vx.begin() - 1;
y2[i] = std::lower_bound(vy.begin(), vy.end(), y2[i] + 1) - vy.begin() - 1;
}
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);
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);
};
for (int i = 0; i < n; i++) {
if (x1[i] == x2[i]) {
if (y1[i] > y2[i]) {
continue;
}
add(x1[i], y1[i]);
add(x2[i], y2[i]);
segx[x1[i]].push_back({y1[i], y2[i]});
} else {
if (x1[i] > x2[i]) {
continue;
}
add(x1[i], y1[i]);
add(x2[i], y2[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());
}
std::vector<int> dx{0, nx - 1};
constexpr int B = 100;
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);
}
}
}
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;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3780kb
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: 3596kb
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: 0ms
memory: 3788kb
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: 0ms
memory: 3648kb
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: 0ms
memory: 3656kb
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: 7020kb
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: 51ms
memory: 17316kb
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: 102ms
memory: 36148kb
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: 192ms
memory: 56996kb
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: 314ms
memory: 90296kb
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: 358ms
memory: 138128kb
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: 312ms
memory: 90416kb
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: 309ms
memory: 89992kb
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: 292ms
memory: 88968kb
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: 318ms
memory: 90648kb
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: 545ms
memory: 106692kb
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: 360ms
memory: 78272kb
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: 1505ms
memory: 268676kb
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: 1460ms
memory: 270192kb
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: 1469ms
memory: 268268kb
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: 1527ms
memory: 270772kb
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: 1411ms
memory: 261912kb
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: 0
Accepted
time: 1440ms
memory: 269672kb
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...
output:
166043
result:
ok answer is '166043'
Test #24:
score: 0
Accepted
time: 1506ms
memory: 269308kb
input:
10000 -4185 4931 -4185 9055 -957 -3447 9708 -3447 4306 -8611 -3799 -8611 7938 -9662 -3454 -9662 -2030 -6055 -1067 -6055 3533 3897 1746 3897 5764 9951 5764 -6035 7178 -3198 7178 8165 -9577 6633 -7052 6633 2133 9608 2133 -5934 -7241 -2537 4939 -2537 -6343 -2783 5590 -2783 -8383 -588 -8383 -2403 -5342 ...
output:
13697
result:
ok answer is '13697'
Test #25:
score: 0
Accepted
time: 1457ms
memory: 270488kb
input:
10000 -5616 -9030 -684 -9030 7371 8296 -9818 8296 2007 1038 2007 7814 5591 -6096 -7752 -6096 -9250 -7645 -9250 2801 -9211 7265 8090 7265 6227 -7435 6227 -3303 9915 5267 9915 7897 6717 -9060 6717 -6918 -4118 2321 -1661 2321 26 4397 26 -6333 1081 -3684 6538 -3684 -590 -893 -6684 -893 3363 4069 4463 40...
output:
7344
result:
ok answer is '7344'
Test #26:
score: 0
Accepted
time: 1429ms
memory: 271360kb
input:
10000 -591 1185 -9301 1185 6739 6983 6309 6983 -4953 -2127 -4953 -8034 68 5905 6407 5905 -3392 -299 -3392 -2914 -4742 711 -4742 -4370 7230 -4244 7230 2354 3322 -4472 3322 9040 3605 8666 8715 8666 6776 -4239 6776 -9111 9895 -3088 6716 -3088 6668 7927 6668 4890 -4864 -5509 -5132 -5509 1162 -4185 1162 ...
output:
15945
result:
ok answer is '15945'
Test #27:
score: 0
Accepted
time: 1465ms
memory: 272356kb
input:
10000 -4869 -4593 -4869 -8737 3467 -4634 3467 -4642 -3060 5121 -3060 -1959 -8204 -3456 -8204 6966 5899 1924 5899 -3643 7901 -9099 -2008 -9099 9822 -1447 9822 6991 -4245 -2255 -4245 -9889 -1022 -6376 1296 -6376 9832 4014 -999 4014 371 6743 371 -9215 5333 -5690 5512 -5690 7665 -1739 7665 3301 6810 -22...
output:
11485
result:
ok answer is '11485'
Test #28:
score: 0
Accepted
time: 1441ms
memory: 270072kb
input:
10000 -1195 -496 -1195 -2622 -2197 -2911 -6283 -2911 7113 -8073 -3721 -8073 -192 -212 -8426 -212 7729 -3151 5467 -3151 2250 -2584 -3661 -2584 -7015 7604 -7015 -9970 -502 5987 7745 5987 -483 -8960 -483 -7337 3187 8247 7437 8247 757 -9569 757 457 -6242 -1178 -5069 -1178 -6470 9595 -2611 9595 -8534 585...
output:
13125
result:
ok answer is '13125'
Test #29:
score: 0
Accepted
time: 1475ms
memory: 270576kb
input:
10000 -1518 1598 -1518 2585 -4806 1513 -4806 1413 -440 3077 -2816 3077 2819 4789 -1885 4789 -1407 -2183 -1407 4559 -3826 766 406 766 4437 4058 4437 -2293 618 -2101 618 3133 3031 -1101 -2095 -1101 -231 -235 -231 -3793 -2279 4593 -2279 -215 -1230 -2670 -1810 -2670 3418 -3693 3418 4603 -1824 -4174 -182...
output:
5576
result:
ok answer is '5576'
Test #30:
score: 0
Accepted
time: 1526ms
memory: 267040kb
input:
10000 1628 -2271 1628 1528 -934 1553 -1519 1553 2273 255 2273 2030 -1072 1572 -1006 1572 -1342 -396 -1342 -1601 1293 -858 -1495 -858 -2062 1820 -2287 1820 -1524 2485 -1524 -2338 -2080 -1596 1081 -1596 -1348 507 -309 507 123 -2149 123 -1577 -2399 1849 -2399 -1992 2397 1740 -1795 1740 -577 -695 -577 4...
output:
4205
result:
ok answer is '4205'
Test #31:
score: 0
Accepted
time: 1479ms
memory: 274760kb
input:
10000 17296 -4451 17296 4192 19985 4827 19985 -2862 19343 -5136 12418 -5136 -2547 8314 -2547 -19468 -7058 18512 -7058 10530 -10460 -3341 11582 -3341 12127 -11134 15794 -11134 7017 4989 3870 4989 -11396 -3243 -8269 -3243 -11220 -7658 11040 -7658 -4270 18587 5486 18587 -16518 18986 -16518 -15160 -2503...
output:
40426
result:
ok answer is '40426'
Test #32:
score: 0
Accepted
time: 1535ms
memory: 275240kb
input:
10000 -18830 -43538 -18830 -38698 7654 12666 7654 3649 -49542 -38985 -49542 -3078 -22398 9235 -22398 23434 -20022 3314 -20022 31786 34935 19301 34935 1757 -39395 -49233 -39395 -30361 -26188 -6709 7882 -6709 -44597 32213 -44597 -32617 29448 34327 29448 21636 48662 15632 16455 15632 -47475 44266 -4747...
output:
100400
result:
ok answer is '100400'
Test #33:
score: 0
Accepted
time: 1527ms
memory: 270928kb
input:
10000 71384 91321 4192 91321 -58131 -78890 6829 -78890 -11187 65474 62707 65474 -53772 -49957 9067 -49957 12088 -74857 -49366 -74857 -12638 66156 -74394 66156 61539 -11123 50664 -11123 -60147 48454 85870 48454 95706 58827 3682 58827 -31692 59832 -66729 59832 -5295 -37887 -5295 34301 87081 -56045 964...
output:
81482
result:
ok answer is '81482'
Test #34:
score: 0
Accepted
time: 1488ms
memory: 271832kb
input:
10000 2418 -6612 2418 2340 9150 -9160 9150 1659 155 4312 155 -8748 6552 2067 6552 -7325 5893 4525 -3498 4525 6082 1998 6082 5047 -5613 -8811 -5613 936 6127 8236 6127 3177 -6822 -1798 2160 -1798 -6270 7778 -6270 -3033 -765 9868 -765 9572 -2825 -9264 4379 -9264 -4545 -5017 4146 -5017 -8043 -4641 -8043...
output:
13713
result:
ok answer is '13713'
Test #35:
score: 0
Accepted
time: 1512ms
memory: 268744kb
input:
10000 7164 -5004 3639 -5004 -399 -8022 -399 9288 -57 -6433 -3605 -6433 9427 -6336 9427 -8460 8316 -9689 8316 9341 -4276 3734 -4119 3734 -2153 2166 -2153 -5270 2845 -1494 6977 -1494 9052 1062 9052 -3980 -3433 -7873 -3433 7085 8526 5524 5329 5524 -4273 -4771 -4052 -4771 -9668 -865 -9668 -1108 -2604 68...
output:
2830
result:
ok answer is '2830'
Test #36:
score: 0
Accepted
time: 1535ms
memory: 269464kb
input:
10000 -6777 2627 -7384 2627 5618 -5900 6848 -5900 -9287 -8259 -9287 3419 -9285 -4001 -9285 5869 4663 9897 6926 9897 6763 -4673 8047 -4673 -7036 1898 -4433 1898 -7929 -9131 -7929 -8704 6219 3072 6219 -7314 2627 7137 466 7137 7223 -4946 3223 -4946 -3585 -1969 -7706 -1969 -9425 9878 -9924 9878 262 -260...
output:
21394
result:
ok answer is '21394'
Test #37:
score: 0
Accepted
time: 1506ms
memory: 270556kb
input:
10000 559 6777 559 7719 -6565 5438 -6565 9257 5625 -8431 5625 7954 -9661 5750 -8445 5750 7851 862 114 862 -7782 -3783 -7782 7827 2905 -1916 2905 9085 3491 4846 7441 4846 4522 4640 3164 4640 8073 6678 8073 -9568 6388 -7703 6388 367 -6904 -4771 -55 -4771 -8523 -1944 -8523 3030 -5030 -785 -5030 356 -70...
output:
9109
result:
ok answer is '9109'
Test #38:
score: 0
Accepted
time: 1505ms
memory: 271540kb
input:
10000 -44051 72925 -40788 72925 68102 -29000 -35187 -29000 40838 -582 4699 -582 49325 31476 49325 -681 -9685 33684 -13288 33684 52844 14063 52844 76608 93980 44245 93980 -8857 74422 66280 74422 -73782 -83307 -14255 -83307 61723 -10595 25726 -10595 -9216 -53992 4481 20063 4481 85619 -53789 85619 -979...
output:
79661
result:
ok answer is '79661'
Test #39:
score: 0
Accepted
time: 155ms
memory: 43368kb
input:
9997 -1 0 -3035 0 -1 1 -6061 1 -1 2 -4277 2 -1 3 -2275 3 -1 4 -2216 4 -1 5 -4401 5 -1 6 -11104 6 -1 7 -9973 7 -1 8 -9519 8 -1 9 -9804 9 -1 10 -3794 10 -1 11 -6541 11 -1 12 -6950 12 -1 13 -4012 13 -1 14 -7541 14 -1 15 -10224 15 -1 16 -2111 16 -1 17 -6189 17 -1 18 -8113 18 -1 19 -7672 19 -1 20 -9342 2...
output:
209994
result:
ok answer is '209994'
Test #40:
score: 0
Accepted
time: 11ms
memory: 4804kb
input:
4630 94606 -99989 94264 -99989 92379 -99989 92181 -99989 84390 -99989 86271 -99989 74063 -99989 72527 -99989 63891 -99989 69168 -99989 60250 -99989 53604 -99989 50668 -99989 52733 -99989 49455 -99989 49073 -99989 48186 -99989 37337 -99989 36191 -99989 31703 -99989 22687 -99989 25138 -99989 21912 -99...
output:
390641
result:
ok answer is '390641'
Test #41:
score: 0
Accepted
time: 6ms
memory: 4648kb
input:
1710 68322 -95430 95409 -95430 52698 -95430 67671 -95430 49968 -95430 7400 -95430 -16103 -95430 3247 -95430 -18656 -95430 -17887 -95430 -49221 -95430 -20825 -95430 -49982 -95430 -77043 -95430 -82232 -95430 -79179 -95430 -97652 -95430 -83012 -95430 72892 -93674 95409 -93674 59969 -93674 69789 -93674 ...
output:
25193
result:
ok answer is '25193'
Test #42:
score: 0
Accepted
time: 425ms
memory: 68484kb
input:
7178 19249 -82086 19249 -99809 48091 -94976 48091 53479 70447 -99809 70447 -77463 -99567 -32219 -50088 -32219 -93156 -50534 -93156 60093 65212 88727 65212 96022 -29752 -20300 -29752 -99809 -60328 -99809 -60328 -37600 -39165 -74243 -87672 -74243 51374 45613 51374 27542 -99567 -28919 -61920 -28919 -42...
output:
52083
result:
ok answer is '52083'
Test #43:
score: 0
Accepted
time: 329ms
memory: 59392kb
input:
9173 -41428 -52844 -27987 -52844 10986 45134 -3466 45134 90186 98952 90186 -98329 -47358 98952 -47358 79344 1815 -12391 1815 98952 -42571 98952 -42571 60381 47955 -98329 47955 98952 94398 -98329 94398 98952 27389 -74243 99983 -74243 -16856 98952 -16856 70779 -98561 -98329 -98561 76935 26755 -66593 2...
output:
143743
result:
ok answer is '143743'
Test #44:
score: 0
Accepted
time: 49ms
memory: 11964kb
input:
7986 28969 65753 28969 65322 -90260 -90828 99442 -90828 25439 77057 25439 76935 -90260 -67337 99442 -67337 99442 10771 -90260 10771 -90260 15577 99442 15577 -90260 -34312 99442 -34312 99442 -35605 12318 -35605 -90260 -38561 99442 -38561 -32519 -57589 -32519 -50328 99442 59859 56307 59859 -90260 5827...
output:
281434
result:
ok answer is '281434'
Test #45:
score: 0
Accepted
time: 43ms
memory: 11728kb
input:
9260 -95959 32295 96908 32295 96908 52785 -95959 52785 -70722 9184 -70722 8715 49567 53831 49567 53866 96908 19810 -95959 19810 -95959 44537 9147 44537 96908 -70063 -95959 -70063 96908 45848 -95959 45848 96908 62316 -95959 62316 14735 76492 -95959 76492 -95959 73146 96908 73146 14735 -62318 -95959 -...
output:
111282
result:
ok answer is '111282'
Test #46:
score: 0
Accepted
time: 184ms
memory: 24936kb
input:
8448 54698 10008 56283 10008 -70966 4667 -77900 4667 71846 11837 71846 20485 73646 13355 82197 13355 52133 61611 58065 61611 -16363 82789 -16363 18010 -75917 26165 -75917 21593 68486 -39249 65030 -39249 41074 -91288 48858 -91288 62131 28264 69299 28264 -26015 -98309 -26015 -83331 -9080 67503 -24926 ...
output:
133408
result:
ok answer is '133408'
Test #47:
score: 0
Accepted
time: 551ms
memory: 134112kb
input:
19997 -1 0 -58889541 0 -1 1 -33637007 1 -1 2 -98386649 2 -1 3 -56452802 3 -1 4 -30183791 4 -1 5 -91875837 5 -1 6 -7678190 6 -1 7 -15180755 7 -1 8 -95990620 8 -1 9 -7507358 9 -1 10 -23954200 10 -1 11 -1697168 11 -1 12 -74282283 12 -1 13 -92331674 13 -1 14 -41024972 14 -1 15 -7021474 15 -1 16 -5342475...
output:
2000019994
result:
ok answer is '2000019994'
Test #48:
score: 0
Accepted
time: 1465ms
memory: 309624kb
input:
20000 -925957029 -999996544 -925957029 999856500 848650338 -999996544 848650338 999856500 637171636 -999996544 637171636 999856500 -999997473 586561058 999783130 586561058 326673347 -999996544 326673347 999856500 93272805 542614151 93272805 999856500 -999997473 219514094 999783130 219514094 -9999974...
output:
3999633647
result:
ok answer is '3999633647'
Test #49:
score: 0
Accepted
time: 1451ms
memory: 289212kb
input:
19999 565477087 -999928875 565477087 999989600 896754241 507943864 999643867 507943864 252729575 -999928875 252729575 999989600 -999967762 658538790 293617239 658538790 282420688 -624795795 999643867 -624795795 920932906 -178746677 999643867 -178746677 -999967762 20753452 999643867 20753452 -9999677...
output:
3999530104
result:
ok answer is '3999530104'
Test #50:
score: 0
Accepted
time: 1376ms
memory: 292436kb
input:
20000 -999746278 851144123 999915837 851144123 -889783683 -999772126 -889783683 999983235 -999746278 514549399 999915837 514549399 -999746278 -257136957 999915837 -257136957 -999746278 -275993181 999915837 -275993181 -999746278 834963835 999915837 834963835 -999746278 -322803369 999915837 -322803369...
output:
3999417476
result:
ok answer is '3999417476'
Test #51:
score: 0
Accepted
time: 1388ms
memory: 292924kb
input:
19999 -999982748 -954765033 999373617 -954765033 -999982748 -383558725 999373617 -383558725 -924722709 -999852294 -924722709 999729268 -999982748 -698115807 999373617 -698115807 -999982748 -153509693 999373617 -153509693 752509165 -999852294 752509165 999729268 -999982748 53654698 999373617 53654698...
output:
3998937927
result:
ok answer is '3998937927'
Test #52:
score: 0
Accepted
time: 1409ms
memory: 294380kb
input:
20000 -999914947 172442644 999979692 172442644 868116789 -999818515 868116789 999791692 -999914947 698387312 999979692 698387312 -999914947 575372611 999979692 575372611 -914647984 792375565 999979692 792375565 -999914947 -978925045 999979692 -978925045 -999914947 -981277607 999979692 -981277607 807...
output:
3999504846
result:
ok answer is '3999504846'
Test #53:
score: 0
Accepted
time: 1510ms
memory: 336020kb
input:
20000 -999993404 -999778368 -999993404 999451782 -999899212 -999778368 -999899212 999451782 -999854904 -999778368 -999854904 999451782 -999779028 -999778368 -999779028 999451782 -999717592 -999778368 -999717592 999451782 -999534628 -999778368 -999534628 999451782 -999498743 -999778368 -999498743 999...
output:
3999216809
result:
ok answer is '3999216809'
Test #54:
score: 0
Accepted
time: 1411ms
memory: 261368kb
input:
19994 -959413924 830016792 999030470 830016792 -197694140 -999863119 -197694140 -6768970 -999768708 645557877 999030470 645557877 727818839 856807198 999030470 856807198 -121331098 -670222258 999030470 -670222258 313260779 -999863119 313260779 999590464 -999768708 390122133 -467855410 390122133 -732...
output:
3998252761
result:
ok answer is '3998252761'
Extra Test:
score: 0
Extra Test Passed