QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19150#1877. Matryoshka DollsPeanut_TangWA 329ms24664kbC++141.8kb2022-01-28 11:50:262022-05-06 04:19:50

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:19:50]
  • 评测
  • 测评结果：WA
  • 用时：329ms
  • 内存：24664kb
查看
  • [2022-01-28 11:50:26]
  • 提交

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()
{
	scanf("%d%d",&n,&m); int i,j,l,r;
	for (i=1; i<=n; i++) scanf("%d",a+i),b[a[i]]=i;
	for (i=1; i<=m; i++) scanf("%d%d",&l,&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=1,E=tp=0; i<=n; i++) L[i]=i-1,R[i]=i+1,E+=Dis(i,R[i]); L[j]=0;
                for (i=1; i<j; i++) Del(a[i]);
		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++) printf("%lld\n",ans[i]);

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

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

input:

1 1
1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 329ms
memory: 24664kb

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

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

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

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

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

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

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

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

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

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

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

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:

91858
16199
172586
11743
13708
1
8484
24808
29010
1959
54245
189822
185142
14619
107305
70306
22856
158766
20226
10226
50230
45130
14245
108754
65247
83894
78485
59
145777
1047
73797
583
96849
154438
95660
132514
45756
64564
4523
53331
32540
40791
3192
264
442
49416
38360
183575
51800
112924
14116
1...

result:

wrong answer 2nd numbers differ - expected: '15668', found: '16199'
English 繁體中文 简体中文

Server Time: 2024-12-02 03:12:05 | OpenSource Project