QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#292605	#6334. Passport	chy12321	100 ✓	352ms	83168kb	C++20	2.0kb	2023-12-28 09:23:06	2023-12-28 09:23:06

Judging History

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

[2023-12-28 09:23:06]
评测

测评结果：100
用时：352ms
内存：83168kb

查看

[2023-12-28 09:23:06]
提交

answer

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 10;

int n, m, idx[N << 2], d1[N << 2], dn[N << 2], dis[N << 2], p[N];

struct Edge {
    int v, w;

    Edge(int v, int w): v(v), w(w) {}
};

vector<Edge> G[N << 2];
deque<int> q;

namespace SGT {
    #define lson pos << 1
    #define rson pos << 1 | 1

    void build(int pos, int l, int r) {
        if (l == r) {idx[pos] = l; return;}
        idx[pos] = ++idx[0]; int mid = (l + r) >> 1;
        build(lson, l, mid), build(rson, mid + 1, r);
        G[idx[lson]].emplace_back(idx[pos], 0), G[idx[rson]].emplace_back(idx[pos], 0);
    }

    void add(int pos, int l, int r, int x, int y, int v) {
        if (x <= l && r <= y) {G[idx[pos]].emplace_back(v, 1); return;}
        int mid = (l + r) >> 1;
        if (x <= mid) add(lson, l, mid, x, y, v);
        if (y > mid) add(rson, mid + 1, r, x, y, v);
    }
}

void bfs(int d[]) {
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        for (Edge e : G[u]) {
            if (d[u] + e.w < d[e.v]) {
                d[e.v] = d[u] + e.w;
                e.w ? q.push_back(e.v) : q.push_front(e.v);
            }
        }
    }
}

bool cmp(const int &a, const int &b) {return dis[a] < dis[b];}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n; SGT::build(1, 1, idx[0] = n);
    for (int i = 1, l, r; i <= n; i++) cin >> l >> r, SGT::add(1, 1, n, l, r, i);
    memset(d1, 0x3f, sizeof(d1)), d1[1] = 0, q.push_back(1), bfs(d1);
    memset(dn, 0x3f, sizeof(dn)), dn[n] = 0, q.push_back(n), bfs(dn);
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; i++) dis[i] = d1[i] + dn[i] - (1 < i && i < n);
    iota(p + 1, p + n + 1, 1), sort(p + 1, p + n + 1, cmp);
    for (int i = 1; i <= n; i++) q.push_back(p[i]);
    bfs(dis); cin >> m;
    while (m--) {
        int x; cin >> x;
        cout << (dis[x] > n ? -1 : dis[x]) << '\n';
    }
    return 0;
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 0ms

memory: 31572kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 8ms

memory: 31624kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 337ms

memory: 75936kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 129ms

memory: 56044kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 0

Accepted

time: 83ms

memory: 50568kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 0

Accepted

time: 53ms

memory: 48444kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 48ms

memory: 55996kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 8ms

memory: 31584kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 6ms

memory: 31612kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 4ms

memory: 31612kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 3ms

memory: 31576kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 0ms

memory: 31572kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 3ms

memory: 31624kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 0ms

memory: 31660kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 3ms

memory: 31656kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 9ms

memory: 31640kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 4ms

memory: 31632kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 0ms

memory: 31656kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 3ms

memory: 31980kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 5ms

memory: 32008kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 3ms

memory: 32152kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 0ms

memory: 32184kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 9ms

memory: 31836kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 7ms

memory: 31936kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 0ms

memory: 31836kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 7ms

memory: 31920kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 0ms

memory: 31996kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 0ms

memory: 32008kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 3ms

memory: 31952kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 7ms

memory: 31836kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 3ms

memory: 31928kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 2500 lines

Test #32:

score: 0

Accepted

time: 3ms

memory: 31936kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 46

Accepted

Test #33:

score: 46

Accepted

time: 352ms

memory: 76236kb

input:

output:

result:

ok 196830 lines

Test #34:

score: 0

Accepted

time: 145ms

memory: 56304kb

input:

output:

result:

ok 199765 lines

Test #35:

score: 0

Accepted

time: 195ms

memory: 83148kb

input:

output:

result:

ok 199851 lines

Test #36:

score: 0

Accepted

time: 175ms

memory: 83168kb

input:

output:

result:

ok 199992 lines

Test #37:

score: 0

Accepted

time: 91ms

memory: 50520kb

input:

output:

result:

ok 200000 lines

Test #38:

score: 0

Accepted

time: 131ms

memory: 57892kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 lines

Test #39:

score: 0

Accepted

time: 47ms

memory: 40984kb

input:

output:

result:

ok 74422 lines

Test #40:

score: 0

Accepted

time: 117ms

memory: 58652kb

input:

output:

result:

ok 198765 lines

Test #41:

score: 0

Accepted

time: 152ms

memory: 66484kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 199636 lines

Extra Test:

score: 0

Extra Test Passed