QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#18820#1877. Matryoshka Dolls1789RE 31ms21056kbC++202.9kb2022-01-27 13:58:142022-05-06 02:45:30

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 02:45:30]
  • 评测
  • 测评结果：RE
  • 用时：31ms
  • 内存：21056kb
查看
  • [2022-01-27 13:58:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	int s=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		s=s*10+c-'0';
		c=getchar();
	}
	return s*f;
}
void write(long long x)
{
	if(x<0)
	putchar('-'),x=-x;
	if(x/10)
	write(x/10);
	putchar(x%10+'0'); 
}
int n,m,s,ns;
int num[500007],block[500007],l[717],r[717];
long long anss[500007];
struct Quest{
	int l,r,dat;
}q[500007];
bool cmp2(Quest x,Quest y)
{
	if(block[x.l]!=block[y.l])
	return block[x.l]<block[y.l];
	if(block[x.l]&1)
	return x.r<y.r;
	return x.r>y.r;
}
int wz[500007],L[500007],R[500007];
set <int> S;
long long ans=0;
int main()
{
	//freopen("rrads.in","r",stdin);
	//freopen("rrads.out","w",stdout); 
	n=read(),m=read();
	s=n/sqrt(m),ns=n/s;
	S.insert(0);
	S.insert(1e9);
	for(int i=1;i<=n;++i)
	num[i]=read(),block[i]=(i-1)/s+1,wz[num[i]]=i;
	for(int i=1;i<=ns;++i)
	l[i]=(i-1)*s+1,r[i]=min(i*s,n);
	for(int i=1;i<=m;++i)
	q[i].l=read(),q[i].r=read(),q[i].dat=i;
	sort(q+1,q+m+1,cmp2);
	int l=1,r=0;
	for(int ii=1;ii<=m;++ii)
	{
		while(r<q[ii].r)
		{
			++r;
			int ll,rr;
			S.insert(num[r]);
			ll=*(--S.find(num[r])),rr=*(++S.find(num[r]));
			if(ll>0&&ll<=n)
			{
				ans+=abs(r-wz[ll]);
				R[ll]=num[r],L[num[r]]=ll;
			}
			if(rr>0&&rr<=n)
			{
				ans+=abs(r-wz[rr]);
				L[rr]=num[r],R[num[r]]=rr;
			}
			if(ll>0&&ll<=n&&rr>0&&rr<=n)
			ans-=abs(wz[ll]-wz[rr]);
		//	cout<<l<<" "<<r<<" "<<ans<<endl;
		}
		while(l>q[ii].l)
		{
			--l;
			int ll,rr;
			S.insert(num[l]);
			ll=*(--S.find(num[l])),rr=*(++S.find(num[l]));
			if(ll>0&&ll<=n)
			{
				ans+=abs(l-wz[ll]);
				R[ll]=num[l],L[num[l]]=ll;
			}
			if(rr>0&&rr<=n)
			{
				ans+=abs(l-wz[rr]);
				L[rr]=num[l],R[num[l]]=rr;
			}
			if(ll>0&&ll<=n&&rr>0&&rr<=n)
			ans-=abs(wz[ll]-wz[rr]);
		//	cout<<l<<" "<<r<<" "<<ans<<endl;
		}
		while(r>q[ii].r)
		{
			R[L[num[r]]]=R[num[r]];
			L[R[num[r]]]=L[num[r]];
			int ll=L[num[r]],rr=R[num[r]];
			if(ll>0&&ll<=n)
			ans-=abs(r-wz[ll]);
			if(rr>0&&rr<=n)
			ans-=abs(r-wz[rr]);
			if(ll>0&&ll<=n&&rr>0&&rr<=n)
			ans+=abs(wz[rr]-wz[ll]);
			S.erase(num[r]);
			L[num[r]]=R[num[r]]=0;
			--r;
			//cout<<l<<" "<<r<<" "<<ans<<endl;
		}
		while(l<q[ii].l)
		{
			R[L[num[l]]]=R[num[l]];
			L[R[num[l]]]=L[num[l]];
			int ll=L[num[l]],rr=R[num[l]];
			if(ll>0&&ll<=n)
			ans-=abs(l-wz[ll]);
			if(rr>0&&rr<=n)
			ans-=abs(l-wz[rr]);
		//	cout<<ans<<endl;
			if(ll>0&&ll<=n&&rr>0&&rr<=n)
			ans+=abs(wz[rr]-wz[ll]);
			S.erase(num[l]);
			L[num[l]]=R[num[l]]=0;
			++l;
		//	cout<<ll<<" "<<rr<<" "<<l<<" "<<r<<" "<<ans<<endl;
		}
		anss[q[ii].dat]=ans;
	}
	for(int i=1;i<=m;++i)
	write(anss[i]),putchar('\n');
	fclose(stdin);
	fclose(stdout);
	return 0;
} 
/*
5 15
5 2 4 3 1
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5
*/
源文件, 语言: C++20

詳細信息

Test #1:

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

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

input:

1 1
1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 31ms
memory: 21056kb

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

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

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

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

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

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

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: -100
Runtime Error

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:

result:
English 繁體中文 简体中文

伺服器時間: 2024-12-02 11:07:17 | 開源專案