QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#455944#1877. Matryoshka DollsmakravWA 300ms300848kbC++204.7kb2024-06-27 03:53:552024-06-27 03:53:55

Judging History

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

  • [2024-06-27 03:53:55]
  • 评测
  • 测评结果：WA
  • 用时：300ms
  • 内存：300848kb
查看
  • [2024-06-27 03:53:55]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int K = 550;
const int N = 100010;

int ans_block[(N + K) / K][K][K];
int SPMIN[(N + K) / K][10][K], SPMAX[(100010 + K) / K][10][K];
int nxt[(N + K) / K][100010];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    vector<int> pos(n + 1);
    for (int i = 0; i < n; i++) {
        pos[a[i]] = i;
    }
    vector<int> bl(n, -1);
    int ind= -1;
    for (int i = 0; i < n; i += K) {
        ind++;
        vector<int> ppos;
        for (int j = i + 1; j <= min(n, i + K); j++) {
            bl[pos[j]] = ind;
            ppos.push_back(pos[j]);
        }
        nxt[ind][n] = n + 1;
        int INDD = ppos.size() - 1;
        for (int j = n - 1; j >= 0; j--) {
            nxt[ind][j] = nxt[ind][j + 1];
            if (bl[j] == ind) nxt[ind][j] = INDD--;
        }
        for (int I = 0; I < ppos.size(); I++) {
            SPMIN[ind][0][I] = a[ppos[I]];
            SPMAX[ind][0][I] = a[ppos[I]];
        }
        for (int j = 1; j < 10; j++) {
            for (int I = 0; I + (1 << j) - 1 < ppos.size(); I++) {
                SPMIN[ind][j][I] = min(SPMIN[ind][j - 1][I], SPMIN[ind][j - 1][I + (1 << (j - 1))]);
                SPMAX[ind][j][I] = max(SPMAX[ind][j - 1][I], SPMAX[ind][j - 1][I + (1 << (j - 1))]);
            }
        }
        sort(ppos.begin(), ppos.end());
        vector<vector<int>> bd_right(ppos.size(), vector<int>(ppos.size())), bd_left(ppos.size(), vector<int>(ppos.size()));
        for (int I = 0; I < ppos.size() - 1; I++) {
            bd_right[I][I] = 1e9;
            bd_left[I][I] = 1e9;
            for (int j = I + 1; j < ppos.size(); j++) {
                bd_right[I][j] = bd_right[I][j - 1];
                bd_left[I][j] = bd_left[I][j - 1];
                if (a[ppos[j]] > a[ppos[I]] && bd_right[I][j] > a[ppos[j]] - a[ppos[I]]) {
                    bd_right[I][j] = a[ppos[j]] - a[ppos[I]];
                }
                if (a[ppos[j]] < a[ppos[I]] && bd_left[I][j] > a[ppos[I]] - a[ppos[j]]) {
                    bd_left[I][j] = a[ppos[I]] - a[ppos[j]];
                }
            }
        }
        vector<vector<int>> ans(ppos.size(), vector<int>(ppos.size()));
        for (int I = ppos.size() - 1; I >= 0; I--) {
            ans[I][I] = 0;
            ans_block[ind][I][I] = ans[I][I];
            for (int j = I - 1; j >= 0; j--) {
                ans[j][I] = ans[j + 1][I];
                int rg = (bd_right[j][I] == 1e9 ? -1 : a[ppos[j]] + bd_right[j][I]);
                int lf = (bd_left[j][I] == 1e9 ? -1 : a[ppos[j]] - bd_left[j][I]);
                if (rg != -1) ans[j][I] += abs(pos[rg] - pos[a[ppos[j]]]);
                if (lf != -1) ans[j][I] += abs(pos[lf] - pos[a[ppos[j]]]);
                if (lf != -1 && rg != -1) ans[j][I] -= abs(pos[lf] - pos[rg]);
                ans_block[ind][j][I] = ans[j][I];
            }
        }
    }
    vector<vector<int>> qrs(q);
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r; l--; r--;
        qrs[i] = {l, r, i};
    }
    sort(qrs.begin(), qrs.end(), [&](vector<int> &x, vector<int> &y) {
        return x[1] < y[1];
    });
    vector<int> Log2(n + 1, 0);
    for (int i = 2; i <= n; i++) Log2[i] = Log2[i / 2] + 1; 
    auto getmax = [&](int block, int l, int r) {
        int lg = Log2[r - l + 1];
        return max(SPMAX[block][lg][l], SPMAX[block][lg][r - (1 << lg) + 1]);
    };
    auto getmin = [&](int block, int l, int r) {
        int lg = Log2[r - l + 1];
        return min(SPMIN[block][lg][l], SPMIN[block][lg][r - (1 << lg) + 1]);
    };
    int IND = 0;

    ind++;
    vector<int> last(ind, -1);
    vector<ll> ANSW(q);
    vector<int> cnt(ind);
    for (int r = 0; r < n; r++) {
        last[bl[r]] = cnt[bl[r]]++;
        while (IND < qrs.size() && qrs[IND][1] == r) {
            int L = qrs[IND][0], R = qrs[IND][1];
            ll ANS = 0;
            for (int j = 0; j < ind; j++) {
                if (nxt[j][L] <= last[j] && last[j] != -1) {
                    ANS += ans_block[j][nxt[j][L]][last[j]];
                }
            }
            int LAST = -1;
            for (int j = 0; j < ind; j++) {
                if (nxt[j][L] <= last[j] && last[j] > -1) {
                    int RG = getmax(j, nxt[j][L], last[j]), LF = getmin(j, nxt[j][L], last[j]);
                    if (LAST != -1) ANS += abs(pos[LF] - pos[LAST]);
                    LAST = RG;
                }
            }
            ANSW[qrs[IND][2]] = ANS;
            IND++;
        }
    }
    for (auto &u : ANSW) cout << u << '\n';
    return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 9576kb

input:

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

output:

7
5
3
1
0

result:

ok 5 number(s): "7 5 3 1 0"

Test #2:

score: 0
Accepted
time: 1ms
memory: 9852kb

input:

1 1
1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 300ms
memory: 300848kb

input:

100000 1
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 ...

output:

4999950000

result:

ok 1 number(s): "4999950000"

Test #4:

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

input:

20 1
12 8 13 10 18 14 1 19 5 16 15 9 17 20 6 2 11 4 3 7
9 18

output:

36

result:

ok 1 number(s): "36"

Test #5:

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

input:

20 10
5 16 11 7 19 8 12 13 17 18 6 1 14 3 4 2 15 20 10 9
7 11
7 13
7 17
11 15
1 7
4 6
1 5
6 14
3 5
9 9

output:

7
16
34
9
20
3
8
22
3
0

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 9740kb

input:

20 50
7 3 13 8 9 18 1 15 12 10 20 11 17 16 2 19 5 4 6 14
3 6
5 15
11 20
10 18
9 20
3 17
13 20
16 17
3 20
4 17
15 18
5 19
3 14
8 20
2 20
1 4
15 19
16 20
5 13
14 17
4 10
6 16
8 16
1 12
4 9
11 15
4 20
8 11
3 16
7 7
3 11
3 7
4 4
5 12
6 20
3 14
6 19
6 19
2 14
2 12
5 6
4 6
8 15
10 19
4 14
1 16
1 20
2 13
3...

output:

6
48
36
24
46
74
17
1
104
64
5
68
44
58
130
5
9
8
30
7
13
48
26
38
11
8
92
5
70
0
28
9
0
20
80
44
58
58
48
36
1
2
20
28
34
76
136
46
1
28

result:

ok 50 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 9732kb

input:

20 100
4 13 20 8 1 18 19 9 17 5 12 7 11 16 6 3 15 10 14 2
4 19
1 6
6 19
4 6
2 17
1 5
11 13
1 15
9 17
9 15
7 20
3 19
10 19
1 10
11 17
10 17
2 18
17 20
12 19
1 3
5 17
7 13
6 18
10 20
1 6
2 17
5 9
4 13
11 13
2 20
7 13
12 17
5 19
17 20
11 19
3 15
3 5
5 11
1 17
10 15
16 20
1 6
2 19
4 12
5 18
9 17
3 6
12 ...

output:

76
16
57
3
84
10
3
74
31
19
59
80
40
44
16
26
94
5
26
2
54
17
53
44
16
84
8
32
3
106
17
12
68
5
30
48
2
16
102
14
9
16
98
28
64
31
6
1
54
20
26
31
74
5
26
3
66
32
36
59
1
26
6
33
35
5
57
1
1
57
24
6
10
68
36
41
34
0
12
8
11
2
62
12
41
10
5
25
0
60
0
44
25
12
8
2
16
36
8
1

result:

ok 100 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 9744kb

input:

20 228
7 3 17 10 16 11 19 5 1 13 20 18 14 2 8 4 6 9 12 15
7 20
2 20
10 13
14 19
1 9
12 20
17 19
9 20
10 12
14 17
4 15
7 16
5 12
13 16
16 18
7 18
1 11
7 17
2 20
6 8
9 17
12 18
7 18
3 4
7 13
1 4
6 12
6 10
3 17
3 4
5 14
7 13
9 20
6 20
2 4
14 17
17 20
1 7
19 20
4 20
14 15
12 16
4 6
4 15
10 11
2 16
2 20
...

output:

66
136
5
9
32
30
2
42
3
5
62
40
28
5
2
50
44
44
136
3
20
14
50
1
16
5
18
10
74
1
44
16
42
90
3
5
3
13
1
108
1
6
3
62
1
94
136
3
14
42
3
80
26
6
54
7
26
26
31
1
74
38
15
14
52
26
14
6
4
7
3
2
70
13
2
44
6
76
26
90
1
66
108
0
28
16
132
18
7
3
14
48
7
15
1
8
9
22
9
18
36
5
70
44
42
3
1
42
0
3
3
8
3
62
...

result:

ok 228 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 9876kb

input:

20 322
3 11 4 1 9 19 7 12 5 17 8 15 10 18 13 2 20 16 14 6
8 14
6 6
3 17
3 16
9 18
7 17
12 13
4 14
12 18
6 13
8 9
3 17
7 20
12 16
10 15
12 16
12 14
16 19
6 7
18 20
6 16
7 14
5 19
12 13
3 14
10 15
11 18
12 20
8 9
1 13
17 18
1 18
4 19
4 9
5 19
4 5
1 2
10 17
11 19
7 14
15 20
20 20
4 7
12 15
7 17
3 13
7 ...

output:

19
0
91
80
37
39
1
48
21
23
1
91
81
10
13
10
3
5
1
2
44
23
87
1
50
13
25
37
1
58
1
119
99
14
87
1
1
21
33
23
15
0
6
7
39
42
36
1
91
3
107
25
1
44
1
0
10
7
1
1
55
3
10
2
34
91
1
51
26
25
75
1
1
18
79
13
1
80
21
16
5
3
0
18
3
7
63
63
66
3
0
5
17
0
21
10
1
3
5
1
6
35
41
29
59
43
21
0
45
3
6
75
1
103
0
...

result:

ok 322 numbers

Test #10:

score: 0
Accepted
time: 1ms
memory: 9796kb

input:

20 1000
16 6 17 1 12 11 5 8 10 19 4 18 2 9 14 7 15 3 20 13
1 6
8 9
9 11
5 18
3 20
2 9
17 18
12 12
12 20
5 17
1 8
10 10
2 9
17 19
1 7
7 15
12 19
2 7
9 14
2 14
1 4
15 17
11 19
2 5
3 12
11 14
11 14
13 17
7 8
9 18
2 11
8 11
1 4
4 8
12 13
12 19
7 16
12 16
11 15
5 9
5 18
2 19
11 15
1 15
4 20
4 9
5 14
5 19...

output:

13
1
3
67
113
21
1
0
34
57
23
0
21
3
19
29
24
15
15
54
5
3
34
7
30
7
7
8
1
39
36
5
5
7
1
24
45
9
9
6
67
113
9
78
95
9
31
76
34
25
78
9
7
9
3
6
21
5
78
55
70
13
51
5
29
9
7
1
14
9
1
3
13
3
94
39
7
4
104
44
17
24
29
85
26
9
49
67
40
5
3
7
65
0
54
76
14
67
7
18
37
7
19
1
5
11
27
21
30
21
7
95
23
15
40
...

result:

ok 1000 numbers

Test #11:

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

input:

20 1000
16 8 20 2 5 9 14 7 19 3 13 1 6 18 10 4 15 17 12 11
9 19
12 12
12 19
15 15
6 17
9 16
1 10
4 19
10 13
11 18
2 7
12 17
18 19
4 15
3 18
3 17
5 11
14 17
4 16
3 13
10 10
12 20
1 1
4 8
3 11
8 15
6 7
9 12
1 16
12 20
2 9
8 9
8 9
8 20
17 18
15 20
11 20
1 3
8 10
2 6
8 18
4 12
7 12
3 18
5 14
14 15
6 10
...

output:

41
0
20
0
53
25
45
91
7
24
13
14
1
63
89
87
21
6
75
51
0
22
0
7
33
29
1
5
101
22
23
1
1
53
1
10
34
3
3
11
43
35
13
89
43
1
7
20
6
33
6
2
1
15
51
41
13
29
1
4
10
51
13
1
16
10
45
19
1
11
3
71
15
22
15
35
87
87
129
23
61
2
33
7
51
0
89
43
3
1
7
71
8
75
7
16
105
19
9
14
43
29
35
33
23
20
29
5
2
3
16
4
...

result:

ok 1000 numbers

Test #12:

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

input:

20 1000
7 16 3 15 5 6 10 20 19 2 13 1 11 4 8 18 12 17 14 9
9 20
17 19
1 13
5 19
18 18
6 8
6 14
3 16
6 16
12 17
9 11
9 20
7 20
3 18
10 13
2 8
6 17
5 7
7 15
3 8
11 13
13 18
6 15
8 18
5 10
6 8
13 20
6 7
10 13
6 20
10 12
12 18
9 12
4 12
16 18
2 5
1 11
3 10
13 18
6 20
2 4
3 8
13 20
17 20
3 13
1 10
1 15
1...

output:

47
3
48
68
0
2
26
82
52
10
3
47
60
94
7
15
60
2
26
11
3
10
42
36
10
2
22
1
7
76
3
12
5
26
3
5
42
20
10
76
3
11
22
6
34
34
82
4
3
11
12
13
1
2
5
1
0
24
16
124
1
9
5
13
90
3
26
6
94
98
86
3
5
14
37
28
38
3
1
30
98
4
0
60
42
0
1
20
6
16
12
1
1
10
11
18
98
24
16
1
4
80
16
26
28
1
124
6
1
40
14
3
16
10
3...

result:

ok 1000 numbers

Test #13:

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

input:

20 1337
10 3 6 8 7 15 4 5 9 19 17 13 1 18 12 16 20 2 11 14
10 14
4 5
9 11
7 14
2 8
7 18
11 18
9 12
2 6
8 15
11 18
12 16
19 19
8 19
12 16
4 11
2 18
1 6
15 19
2 12
4 9
3 5
16 20
10 14
3 9
10 10
7 17
6 11
8 10
3 4
6 18
7 12
1 15
7 16
16 17
3 16
6 12
4 15
10 17
13 19
4 20
18 19
13 14
3 16
8 10
3 16
1 14...

output:

9
1
3
19
16
50
26
5
6
23
26
11
0
56
11
19
84
12
7
34
13
3
7
9
17
0
40
11
2
1
62
7
73
33
1
57
17
43
28
16
94
1
1
57
2
57
67
74
5
5
24
60
4
76
52
3
1
15
9
16
1
19
15
5
2
35
60
5
35
92
22
3
1
0
3
9
6
6
6
73
54
36
9
14
11
17
0
108
73
67
83
4
44
41
14
83
0
3
1
17
64
4
17
17
45
11
3
15
50
23
4
1
30
17
74
...

result:

ok 1337 numbers

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 14964kb

input:

1000 1000
40 954 881 24 748 110 805 978 860 472 882 621 530 586 488 928 150 443 553 402 177 702 871 214 778 7 489 874 812 754 90 806 206 60 283 243 416 720 650 539 763 588 570 114 658 396 19 970 372 743 587 885 527 296 3 900 313 968 772 280 691 349 37 178 714 49 122 823 143 632 662 387 88 176 400 63...

output:

91620
15817
172647
12165
13618
535
8258
25370
29391
1525
53838
190052
185733
14174
106855
70067
22983
158798
20062
10732
50395
45299
14428
108761
65121
84182
79017
577
145691
636
73503
611
97009
154576
95694
132309
45565
64953
4482
53332
33196
41317
3495
1006
83
49390
38486
184384
51870
112765
14079...

result:

wrong answer 1st numbers differ - expected: '91858', found: '91620'
English 繁體中文 简体中文

伺服器時間: 2024-11-30 02:27:37 | 開源專案