QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#24719#1877. Matryoshka Dollszzy0922WA 14ms16140kbC++2.9kb2022-04-02 15:43:582022-04-30 06:31:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 06:31:25]
  • 评测
  • 测评结果：WA
  • 用时：14ms
  • 内存：16140kb
查看
  • [2022-04-02 15:43:58]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21],*p1 = buf,*p2 = buf;
inline int read()
{
    char c = getchar();
    int x = 0;
    bool f = 0;
    for(;!isdigit(c); c = getchar()) f ^= !(c ^ 45);
    for(;isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    if (f) x = -x; 
    return x;
}

int n, m, a[500005], b[500005], pos[500005];
long long anslist[500005];
int len;
struct query{
    int l, r, idx;
    bool operator<(query a) {
        if (l / len == a.l / len) return r > a.r;
        else return l / len < a.l / len; 
    }
}q[500005];

struct node {
    int val, next, prev;
}lis[500005];
#define head lis[0]
#define tail lis[n + 1]
long long ans, tmp, now;

void del(int p, long long& x) {
    if (lis[p].prev == 0) x -= abs(p - lis[p].next);
    else if (lis[p].next == n + 1) x -= abs(p - lis[p].prev);
    else if (lis[p].prev == 0 && lis[p].next == n + 1) x = 0;
    else x = x - abs(p - lis[p].prev) - abs(p - lis[p].next) + abs(lis[p].next - lis[p].prev);
    lis[lis[p].prev].next = lis[p].next;
    lis[lis[p].next].prev = lis[p].prev;
}

void rcv(int p) {
    lis[lis[p].prev].next = p;
    lis[lis[p].next].prev = p;
}

int main() {
    scanf("%d%d", &n, &m);
    len = n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        lis[i].val = a[i];
    for (int i = 1; i <= n; i++)
        pos[a[i]] = i;
    memcpy(b, a, sizeof a);
    sort(b + 1, b + n + 1);
    for (int i = 1; i < n; i++) {
        ans += abs(pos[b[i]] - pos[b[i + 1]]);
    }
    head.next = pos[b[1]];
    lis[pos[b[1]]].prev = 0;
    for (int i = 1; i < n; i++) {
        lis[pos[b[i]]].next = pos[b[i + 1]];
        lis[pos[b[i + 1]]].prev = pos[b[i]];
    }
    tail.prev = pos[b[n]];
    lis[pos[b[n]]].next = n + 1;
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &q[i].l, &q[i].r);
    for (int i = 1; i <= m; i++)
        q[i].idx = i;
    sort (q + 1, q + m + 1);
    now = ans;
    //for (int i = 1; i <= m; i++) printf("%d %d\n", q[i].l, q[i].r);
    //cout << ans;
    for (int i = 1, l = 1, r = n; i <= m; i++) {
        if (q[i].l / len != q[i - 1].l /len) {
            while (l < (q[i].l - 1) / len * len + 1) del(l++, now);
            r = n;
            tmp = ans = now;
        }
        // l = 1, r = n;
        // ans = now;
        while (r > q[i].r) del(r--, ans);
        tmp = ans;
        while (l < q[i].l) del(l++, /*ans*/tmp);
        anslist[q[i].idx] = /*ans*/tmp;
        while (l > (q[i].l - 1) / len * len + 1) rcv(--l);
      //  printf("%d %d\n", q[i].l, q[i].r);
        //printf("%lld\n", anslist[q[i].idx]);
    }
    for (int i = 1; i <= m; i++) printf("%lld\n", anslist[i]);
    
    return 0;
}/*
7
16
34
9
20
3
8
22
3
0
*/
Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 16048kb

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: 0ms
memory: 16140kb

input:

1 1
1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 14ms
memory: 15056kb

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: 3ms
memory: 16068kb

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: 2ms
memory: 16024kb

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

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: 3ms
memory: 15936kb

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: 3ms
memory: 16052kb

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: -100
Wrong Answer
time: 0ms
memory: 14004kb

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
3
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
20
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:

wrong answer 42nd numbers differ - expected: '0', found: '3'
English 繁體中文 简体中文

Server Time: 2024-11-30 02:28:07 | OpenSource Project