QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#179924#7224. The Imaginary Girlfrienducup-team004AC ✓1535ms336020kbC++208.9kb2023-09-15 13:32:292023-09-15 13:32:30

Judging History

你现在查看的是最新测评结果

  • [2023-09-15 13:32:30]
  • 评测
  • 测评结果:AC
  • 用时:1535ms
  • 内存:336020kb
  • [2023-09-15 13:32:29]
  • 提交

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