QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179040#7224. The Imaginary Girlfrienducup-team004ML 1137ms276132kbC++208.4kb2023-09-14 17:06:532023-09-14 17:06:53

Judging History

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

  • [2023-09-14 17:06:53]
  • 评测
  • 测评结果:ML
  • 用时:1137ms
  • 内存:276132kb
  • [2023-09-14 17:06:53]
  • 提交

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]) {
                auto itl = h.lower_bound(l + 1);
                auto itr = h.lower_bound(r);
                if (itl != itr) {
                    while (itl != itr) {
                        add(x, *itl);
                        itl = h.erase(itl);
                    }
                    itl = h.lower_bound(l);
                    while (itl != h.end() && *itl <= r) {
                        add(x, *itl);
                        itl++;
                    }
                }
            }
        }
        for (auto y : ys) {
            h.insert(y);
        }
        for (int x = xr - 1; x > xl; x--) {
            for (auto [l, r] : segx[x]) {
                auto itl = h.lower_bound(l + 1);
                auto itr = h.lower_bound(r);
                if (itl != itr) {
                    while (itl != itr) {
                        add(x, *itl);
                        itl = h.erase(itl);
                    }
                    itl = h.lower_bound(l);
                    while (itl != h.end() && *itl <= r) {
                        add(x, *itl);
                        itl++;
                    }
                }
            }
        }
    }
    
    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::vector<int>> adj(V);
    std::vector<i64> dis(V, -1);
    
    auto addEdge = [&](int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(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 (auto y : adj[x]) {
            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: 1ms
memory: 3540kb

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: 3468kb

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: 3480kb

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: 3480kb

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: 1ms
memory: 3668kb

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: 9ms
memory: 6048kb

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: 29ms
memory: 13228kb

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: 68ms
memory: 24944kb

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: 136ms
memory: 40144kb

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: 198ms
memory: 61400kb

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: 529ms
memory: 205240kb

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: 191ms
memory: 62072kb

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: 190ms
memory: 61456kb

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: 194ms
memory: 61392kb

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: 214ms
memory: 63456kb

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: 1137ms
memory: 276132kb

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: 1058ms
memory: 264076kb

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: -100
Memory Limit Exceeded

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: