QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#292153#6334. PassportMax_s_xaM6 318ms115184kbC++145.2kb2023-12-27 19:48:152023-12-27 19:48:16

Judging History

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

  • [2023-12-27 19:48:16]
  • 评测
  • 测评结果:6
  • 用时:318ms
  • 内存:115184kb
  • [2023-12-27 19:48:15]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 2e5 + 10, MAXM = 4e5 + 10;

int n, Q, al[MAXN], ar[MAXN];
int m, idx[MAXN], id[MAXM];

vector < pair <int, int> > e[MAXM], re[MAXM];
inline void AddEdge(int u, int v, int w)
{
    // cout << u << " " << v << " " << w << "\n";
    e[u].push_back(make_pair(v, w));
    re[v].push_back(make_pair(u, w));
}

int tr[MAXN << 2];
void Build(int cur, int l, int r)
{
    tr[cur] = ++m;
    if (l == r) idx[l] = m;
    else
    {
        int mid = l + r >> 1;
        Build(cur << 1, l, mid), Build(cur << 1 | 1, mid + 1, r);
        AddEdge(tr[cur], tr[cur << 1], 0), AddEdge(tr[cur], tr[cur << 1 | 1], 0);
    }
}
void Update(int cur, int l, int r, int x, int y, int k)
{
    if (x <= l && r <= y) AddEdge(idx[k], tr[cur], 1);
    else
    {
        int mid = l + r >> 1;
        if (x <= mid) Update(cur << 1, l, mid, x, y, k);
        if (y > mid) Update(cur << 1 | 1, mid + 1, r, x, y, k);
    }
}

int dis1[MAXM], dis2[MAXM];
deque <int> dq;

int main()
{
    // freopen("C.in", "r", stdin);
    // freopen("C.out", "w", stdout);
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n);
    Build(1, 1, n);
    for (int i = 1; i <= n; i++) Read(al[i]), Read(ar[i]), Update(1, 1, n, al[i], ar[i], i);
    m++;
    for (int i = 1; i <= n; i++)
        if (al[i] == 1) re[m].push_back(make_pair(idx[i], 1));
    for (int i = 1; i <= m; i++) dis1[i] = 1e9;
    dis1[m] = 0, dq.push_front(m);
    while (!dq.empty())
    {
        int u = dq.front(); dq.pop_front();
        for (auto t : re[u])
        {
            int v = t.first, w = t.second;
            if (dis1[v] > dis1[u] + w)
            {
                dis1[v] = dis1[u] + w;
                if (!w) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
    // for (int i = 1; i <= n; i++) cout << dis1[idx[i]] << " "; cout << "\n";
    re[m].clear();
    for (int i = 1; i <= n; i++)
        if (ar[i] == n) re[m].push_back(make_pair(idx[i], 1));
    for (int i = 1; i <= m; i++) dis2[i] = 1e9;
    dis2[m] = 0, dq.push_front(m);
    while (!dq.empty())
    {
        int u = dq.front(); dq.pop_front();
        for (auto t : re[u])
        {
            int v = t.first, w = t.second;
            if (dis2[v] > dis2[u] + w)
            {
                dis2[v] = dis2[u] + w;
                if (!w) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
    // for (int i = 1; i <= n; i++) cout << dis2[idx[i]] << " "; cout << "\n";
    m--;
    // for (int i = 1; i <= m; i++) cout << dis1[i] << " "; cout << "\n";
    // for (int i = 1; i <= m; i++) cout << dis2[i] << " "; cout << "\n";
    for (int i = 1; i <= m; i++) dis1[i] += dis2[i] - 1, id[i] = i;
    sort(id + 1, id + m + 1, [&](int x, int y) {return dis1[x] < dis1[y];});
    for (int i = 1; i <= m; i++)
    {
        for (auto t : re[id[i]])
        {
            int v = t.first, w = t.second;
            dis1[v] = min(dis1[v], dis1[id[i]] + w);
        }
    }
    // for (int i = 1; i <= m; i++) cout << dis1[i] << " "; cout << "\n";
    Read(Q);
    int x;
    while (Q--)
    {
        Read(x);
        Write((dis1[idx[x]] >= 1e9 ? -1 : dis1[idx[x]]), '\n');
    }
    return 0;
}

詳細信息

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 6ms
memory: 32444kb

input:

2
1 1
1 2
1
1

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 30172kb

input:

2
1 2
2 2
1
1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 302ms
memory: 114384kb

input:

196001
1 408
2 37822
1 1221
1 160899
4 62751
3 21706
2 4118
8 70696
8 4916
3 24286
9 443
8 171744
11 170980
7 3541
12 16428
8 71164
1 186827
11 234
2 23141
4 17143
21 9522
10 24
19 15936
3 15884
17 426
14 3188
17 168317
4 1560
25 35
16 39439
21 122
4 17507
8 97645
11 824
25 59856
30 9265
7 151420
37...

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 163ms
memory: 73220kb

input:

198001
1 17
1 19
1 4
2 20
3 15
6 10
1 20
3 9
3 9
10 19
6 27
8 29
12 24
3 23
8 23
16 19
11 23
1 19
13 30
19 32
4 28
15 33
23 33
8 36
16 30
23 40
11 42
27 34
20 30
21 36
31 39
30 35
32 33
29 48
27 43
33 41
25 53
28 51
29 56
37 55
35 54
36 52
35 44
31 58
36 54
42 56
47 49
41 59
37 64
44 50
34 55
41 56
...

output:

15219

result:

ok single line: '15219'

Test #5:

score: 0
Accepted
time: 85ms
memory: 60508kb

input:

200000
1 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
9 11
10 12
11 13
12 14
13 15
14 16
15 17
16 18
17 19
18 20
19 21
20 22
21 23
22 24
23 25
24 26
25 27
26 28
27 29
28 30
29 31
30 32
31 33
32 34
33 35
34 36
35 37
36 38
37 39
38 40
39 41
40 42
41 43
42 44
43 45
44 46
45 47
46 48
47 49
48 50
49 51
50 52
51 53...

output:

199999

result:

ok single line: '199999'

Test #6:

score: 0
Accepted
time: 48ms
memory: 61396kb

input:

195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195000
1 195...

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 78ms
memory: 74536kb

input:

156789
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 78394
1 783...

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 16
Accepted
time: 6ms
memory: 32280kb

input:

2
1 1
1 2
1
2

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 28184kb

input:

2
1 2
2 2
1
2

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 28136kb

input:

6
1 1
2 2
1 3
3 5
5 6
1 6
1
4

output:

3

result:

ok single line: '3'

Test #11:

score: 0
Accepted
time: 0ms
memory: 28200kb

input:

9
1 1
2 2
3 3
1 4
2 8
5 7
4 9
8 8
9 9
1
6

output:

3

result:

ok single line: '3'

Test #12:

score: 0
Accepted
time: 0ms
memory: 30200kb

input:

9
1 1
2 2
3 3
1 4
2 8
4 9
5 7
8 8
9 9
1
7

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 4ms
memory: 28176kb

input:

10
1 1
2 2
3 3
2 10
1 6
3 8
1 8
6 8
3 9
10 10
1
4

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 2ms
memory: 28228kb

input:

285
1 13
1 16
3 16
3 25
3 94
5 100
2 92
7 10
9 10
1 270
11 11
9 93
5 43
4 115
11 15
10 66
16 20
16 58
16 22
3 124
15 31
1 59
23 23
24 24
19 28
22 126
27 27
20 89
16 218
24 42
10 135
21 156
8 187
27 265
34 35
34 41
15 233
33 107
38 44
5 284
41 42
13 169
33 51
5 81
41 89
44 52
43 50
23 86
42 62
4 95
4...

output:

4

result:

ok single line: '4'

Test #15:

score: 0
Accepted
time: 0ms
memory: 28440kb

input:

296
1 1
1 7
2 6
2 12
4 5
5 8
1 13
6 13
5 17
2 13
3 13
11 17
13 20
10 21
9 16
11 22
12 19
14 19
14 19
12 28
14 23
20 25
15 23
18 31
20 32
20 26
21 33
24 32
22 37
29 35
29 36
31 38
25 34
32 35
34 39
36 37
29 42
36 46
39 43
40 44
33 46
41 48
43 51
39 45
44 47
43 50
41 53
44 52
43 52
45 51
47 58
48 59
5...

output:

49

result:

ok single line: '49'

Test #16:

score: -16
Wrong Answer
time: 0ms
memory: 28220kb

input:

300
1 300
1 300
1 300
2 300
1 299
4 299
5 296
6 298
7 294
7 295
9 292
9 291
11 290
12 291
12 292
13 287
14 286
16 285
17 284
18 284
19 282
20 281
21 281
21 280
21 278
24 277
24 276
26 275
27 274
27 273
29 287
30 271
28 273
27 269
33 268
34 268
31 284
30 265
37 265
38 264
38 264
40 261
40 260
40 260
...

output:

17

result:

wrong answer 1st lines differ - expected: '10', found: '17'

Subtask #3:

score: 0
Wrong Answer

Test #19:

score: 24
Accepted
time: 3ms
memory: 28816kb

input:

2337
1 3
2 77
1 1397
2 222
3 62
6 1896
7 10
6 950
9 9
10 16
11 455
9 588
13 16
7 1245
9 1342
8 1727
7 122
11 653
9 1094
2 57
11 81
19 1290
6 1584
16 79
14 215
21 61
27 27
16 1458
16 198
26 180
31 31
11 240
33 36
11 121
34 1542
9 1752
14 456
36 43
36 2244
40 40
4 517
42 662
31 1350
33 162
30 843
28 1...

output:

4

result:

ok single line: '4'

Test #20:

score: 0
Accepted
time: 0ms
memory: 32768kb

input:

2486
1 12
2 8
1 7
3 12
2 11
3 15
1 8
4 11
9 15
3 21
11 13
4 15
9 21
9 19
5 15
8 20
8 25
16 24
11 29
11 23
18 23
14 32
17 24
13 27
15 30
21 34
16 29
20 35
19 32
29 34
20 39
21 43
29 40
28 43
26 44
31 45
28 43
35 38
30 40
37 46
40 43
42 42
42 45
43 54
39 51
40 51
45 54
46 57
39 53
47 53
47 54
41 59
49...

output:

314

result:

ok single line: '314'

Test #21:

score: -24
Wrong Answer
time: 3ms
memory: 29160kb

input:

2500
1 2500
1 2500
1 2500
2 2500
2 2499
3 2498
5 2496
6 2495
7 2495
8 2493
8 2492
6 2492
11 2491
12 2489
12 2490
12 2491
15 2486
15 2485
17 2484
18 2483
15 2482
20 2483
21 2481
19 2479
23 2481
23 2477
21 2477
25 2476
27 2474
28 2473
29 2472
30 2475
31 2470
30 2469
33 2468
32 2467
33 2466
33 2466
33 ...

output:

115

result:

wrong answer 1st lines differ - expected: '60', found: '115'

Subtask #4:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 3ms
memory: 30920kb

input:

2419
1 883
1 29
3 41
4 2201
1 808
6 45
7 1456
6 134
6 1372
1 1776
4 441
7 208
5 28
4 604
7 56
9 617
8 2115
15 60
13 456
10 2071
18 23
18 39
5 39
21 35
4 75
25 44
24 640
21 30
4 860
30 31
18 78
32 779
1 927
33 34
19 59
34 181
21 502
23 155
39 39
2 254
30 641
42 50
10 2000
41 2220
18 632
35 48
27 905
...

output:

3
3
3
3
3
3
3
3
3
2
3
3
3
3
3
3
3
3
3
3
4
3
3
4
3
4
3
4
3
4
3
3
3
4
3
4
3
4
-1
3
3
4
3
3
3
4
3
3
3
3
3
3
-1
3
3
4
4
3
-1
3
3
3
3
4
4
3
3
4
4
3
3
4
5
4
3
3
4
4
3
4
4
3
4
3
4
3
-1
-1
3
3
3
3
4
3
3
3
3
4
4
4
3
3
4
3
4
4
3
3
4
4
3
4
3
3
4
3
4
4
3
3
3
4
3
3
4
3
4
-1
4
3
3
3
4
4
3
4
4
4
3
4
3
4
-1
4
4
4
3...

result:

wrong answer 18th lines differ - expected: '4', found: '3'

Subtask #5:

score: 0
Wrong Answer

Test #33:

score: 0
Wrong Answer
time: 318ms
memory: 115184kb

input:

196830
1 67357
2 183304
3 23390
4 54
1 145887
3 27807
3 12376
1 1013
3 113274
3 191874
6 23342
9 2113
13 94245
3 141449
10 1727
3 51
17 99028
6 193803
8 7452
6 121537
9 23658
18 611
6 4756
4 5141
8 8547
8 66922
13 7021
9 72
3 53043
16 167381
2 15530
5 192
33 33
9 92655
10 36182
20 19992
36 24454
1 6...

output:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
-1
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
4
3
3
3
3
4
3
3
3
3
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
5
3
3
3
3
3
4
3
3
3
3
3
3
3
3
4
3
3
-1
3
3
3
3
3
3
3
3
3
4
3
3
3
3
3
3
4
-1
3
4
3
4
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3...

result:

wrong answer 4th lines differ - expected: '4', found: '3'