QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19131#1877. Matryoshka DollsPeanut_TangWA 63ms23636kbC++141.7kb2022-01-28 11:33:092022-05-06 04:18:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 04:18:19]
  • 评测
  • 测评结果：WA
  • 用时：63ms
  • 内存：23636kb
查看
  • [2022-01-28 11:33:09]
  • 提交

answer

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define pb push_back
const int N=5e5+5,B=120;

namespace IO
{
	const int S=1<<20|500; char I[S+5],*s,*t,O[S+5],*o; int p[40],P;

	il char Gc(){if (t==s){t=(s=I)+fread(I,1,1<<20,stdin); if (t==s) return EOF;} return *s++;}

	template<class T> il void Read(T &x)
	{
		char c; while ((c=Gc())<48||c>57); x=c^48;
		while ((c=Gc())>47&&c<58) x=(x<<3)+(x<<1)+(c^48);
	}

	il void Fs(){if (o-O) fwrite(O,1,o-O,stdout); o=O;}
	
	il void Pc(char c){if (*o++=c,o-O==S) Fs();}

	template<class T> il void Print(T x){T y; do y=x/10,p[P++]=x-10*y;while (x=y); while (P) Pc(p[--P]^48);}
	
	struct F{F(){o=O;} ~F(){Fs();}}FF;
}
using IO::Read; using IO::Print; using IO::Pc;

int n,m,a[N],b[N],st[N],tp,L[N],R[N]; ll E,ans[N]; struct node{int l,r,o;}; std::vector<node> g[N]; 

il int Dis(int x,int y){return !x||x>n||!y||y>n?0:std::abs(b[x]-b[y]);}

il void Del(int x){st[++tp]=x,E+=Dis(L[x],R[x])-Dis(x,L[x])-Dis(x,R[x]),L[R[x]]=L[x],R[L[x]]=R[x];}

il void Undo(){int x=st[tp--]; E+=Dis(x,L[x])+Dis(x,R[x])-Dis(L[x],R[x]),L[R[x]]=x,R[L[x]]=x;}

int main()
{
	Read(n),Read(m); int i,j,l,r;
	for (i=1; i<=n; i++) Read(a[i]),b[a[i]]=i;
	for (i=1; i<=m; i++) Read(l),Read(r),g[(l-1)/B+1].pb({l,r,i});

	for (j=1; j<=n; j+=B)
	{
		std::vector<node> &h=g[(j-1)/B+1]; std::sort(h.begin(),h.end(),[](const node &a,const node &b){return a.r==b.r?(a.l==b.l?a.o<b.o:a.l<b.l):a.r>b.r;});
		for (i=j,E=tp=0; i<=n; i++) L[i]=i-1,R[i]=i+1,E+=Dis(i,R[i]); L[j]=0;
		l=j,r=n; for (node v:h)
		{
			for ( ; r>v.r; r--) Del(a[r]);
			for ( ; l<v.l; l++) Del(a[l]);
			for (ans[v.o]=E; l>j; l--) Undo();
		}
	}
	for (i=1; i<=m; i++) Print(ans[i]),Pc('\n');

	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

1 1
1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 63ms
memory: 23284kb

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

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

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

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

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: 5ms
memory: 23636kb

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: 10ms
memory: 22384kb

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

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

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

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

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

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:

160246
24862
172586
8761
10614

result:

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

Server Time: 2024-11-29 22:31:25 | OpenSource Project