QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19149#1877. Matryoshka DollsPeanut_TangWA 63ms24160kbC++141.7kb2022-01-28 11:48:332022-05-06 04:19:47

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:47]
  • 评测
  • 测评结果：WA
  • 用时：63ms
  • 内存：24160kb
查看
  • [2022-01-28 11:48:33]
  • 提交

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=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++) 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: 23248kb

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

input:

1 1
1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

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

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

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

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

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

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

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

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

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

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

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

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
-69651
-5640
22372
24577
-48952
120601
253026
228561
-2736
131871
107208
19258
224886
22178
-13270
70970
68096
2537
172332
156217
133132
88319
-62591
159121
-30769
92159
-57353
107117
154438
136830
132514
88270
90500
-24669
53331
39892
40791
-26479
-57185
-53123
94252
...

result:

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

Server Time: 2024-12-02 03:20:16 | OpenSource Project