UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212305#3814. T4drdilyor30779ms6480kbC++111.7kb2024-10-13 18:29:402024-10-13 19:40:20

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int n;
int a[500005],b[500005];
bool c[500005];
bool d[500005];
signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	bool inc=is_sorted(a+1,a+n+1)&&is_sorted(b+1,b+n+1);
	for(int i=2;i<=n;i++)c[i]=(a[i]>b[i-1]);
	for(int i=3;i<=n;i++)d[i]=c[i]&&c[i-1],d[i]+=d[i-1];
	int q=read();
	while(q--){
		int l=read(),r=read();
		if(inc){
			if(a[r]>b[r-1]){cout<<"No\n";continue;}
			if(a[l+1]>b[l]){cout<<"No\n";continue;}
			bool ok=1;
			if(d[r]-d[l+1])ok=0;
			if(ok)cout<<"Yes\n";
			else cout<<"No\n";
			continue;
		}
		//i->j 有边. a[i]>b[j] && i!=j.
		//有没有二分图匹配
		//其中任意找若干个顶点, 有边的>=顶点个数.
		vector<pair<int,int>> v;
		for(int i=l;i<=r;i++)v.push_back(make_pair(b[i],a[i]));
		sort(v.begin(),v.end());
		for(int i=0;i<=r-l;i++){
			if(i>=1)v[i].second=max(v[i].second,v[i-1].second);
		}
		if(v[r-l].first>v[r-l-1].second){
			cout<<"No\n";continue;
		}
		if(v[1].first>v[0].second){
			cout<<"No\n";continue;
		}
		bool ok=1;
		for(int i=1;i<r-l;i++){
			if(v[i].first>v[i-1].second&&v[i+1].first>v[i].second){
				ok=0;
			}
			//它能配到 [0,i-1]
			//[0,i-1] 也是. 也就是说 a[0,i] max <= b[0,i-1] max.
		}
        cout<<(ok?"Yes":"No")<<"\n";
	}
	//1 3 5 9 10 11
	//4 8 6 20 19 17
	//3 8 5
	//2 6 1
	//1 2 6
	//5 3 8
	return 0;
}
//look at my code
//my code is amazing
源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 0ms
memory: 1184kb

input:

10
13 14 16 18 17 19 20 8 6 4
7 12 15 2 11 10 9 3 5 1
10
2 3
1 6
1 7
5 8
1 10
2 6
5 10
3 6
3 7
4 7

output:

No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

10
12 19 15 20 14 9 4 13 17 16
11 18 7 5 10 8 3 1 2 6
10
6 10
2 6
6 7
3 8
1 8
7 8
6 8
4 5
1 7
4 5

output:

Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes

result:

ok 10 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

10
15 8 12 19 6 10 16 18 20 17
13 3 5 14 1 4 9 7 2 11
10
1 3
2 6
5 7
1 4
2 7
1 2
2 5
1 3
2 6
4 5

output:

No
No
Yes
Yes
Yes
No
No
No
No
No

result:

ok 10 tokens

Test #4:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

10
15 9 13 20 17 19 8 3 10 16
11 7 5 18 2 12 6 1 4 14
10
1 2
4 7
6 7
7 10
3 6
6 10
6 10
6 7
1 3
1 2

output:

No
Yes
No
No
Yes
No
No
No
Yes
No

result:

ok 10 tokens

Test #5:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

7
14 7 5 8 12 10 13
4 6 3 2 11 9 1
10
4 5
3 7
1 5
1 3
5 6
3 7
3 7
4 7
5 7
4 5

output:

No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No

result:

ok 10 tokens

Test #6:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

10
14 2 10 19 4 20 16 15 8 17
13 1 9 7 3 18 12 11 6 5
10
8 9
1 9
7 10
2 6
9 10
5 8
1 2
1 9
2 3
6 8

output:

No
No
Yes
No
Yes
No
No
No
No
No

result:

ok 10 tokens

Test #7:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

10
9 12 19 5 13 17 7 15 10 20
8 1 18 2 4 16 6 14 3 11
10
1 8
3 6
2 3
2 3
7 9
5 9
3 8
7 10
5 9
4 8

output:

No
No
No
No
No
No
No
Yes
No
No

result:

ok 10 tokens

Test #8:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

10
20 11 4 9 19 15 8 13 14 17
3 10 1 6 18 12 7 2 5 16
10
4 5
4 8
3 10
4 10
4 6
2 9
3 10
4 8
3 5
7 10

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 tokens

Test #9:

score: 0
Accepted
time: 1ms
memory: 1184kb

input:

10
15 17 20 12 11 2 18 8 14 16
13 10 19 3 9 1 6 7 4 5
10
2 10
1 9
2 9
2 10
2 9
2 9
2 9
1 9
1 9
2 9

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 tokens

Test #10:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

10
14 20 11 10 6 15 18 12 4 17
7 19 9 5 2 3 13 8 1 16
10
1 10
1 9
2 10
1 8
2 9
3 10
1 7
2 8
3 9
4 10

output:

No
No
No
No
No
Yes
No
No
Yes
Yes

result:

ok 10 tokens

Test #11:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

10
4 18 20 12 2 10 6 16 8 14
3 17 19 11 1 9 5 15 7 13
10
3 6
6 10
2 10
1 10
1 4
3 9
6 9
6 10
3 10
4 5

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 tokens

Test #12:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

10
14 12 18 17 20 15 19 16 13 11
6 5 7 9 4 10 2 3 1 8
10
3 5
3 9
3 7
3 4
3 5
9 10
1 8
3 10
1 10
4 6

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #13:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

10
17 19 8 20 7 15 10 3 18 6
14 16 1 13 4 12 9 2 11 5
10
3 10
4 9
3 5
8 9
6 9
3 8
5 7
4 5
3 4
2 5

output:

No
No
No
No
No
No
No
No
No
Yes

result:

ok 10 tokens

Test #14:

score: 0
Accepted
time: 0ms
memory: 1180kb

input:

2
4 3
2 1
1
1 2

output:

Yes

result:

ok "Yes"

Test #15:

score: 0
Accepted
time: 0ms
memory: 1144kb

input:

2
2 4
1 3
1
1 2

output:

No

result:

ok "No"

Test #16:

score: -10
Wrong Answer
time: 0ms
memory: 1148kb

input:

3
4 5 6
1 2 3
1
1 3

output:

No

result:

wrong answer 1st words differ - expected: 'Yes', found: 'No'

Subtask #2:

score: 10
Accepted

Test #17:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

15
29 20 30 4 9 2 24 19 17 25 18 28 21 6 23
26 10 27 3 8 1 14 15 11 16 12 22 7 5 13
10
8 14
5 15
9 1...

output:

No
No
Yes
No
Yes
No
No
Yes
No
Yes

result:

ok 10 tokens

Test #18:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

18
28 31 8 25 36 11 10 32 33 34 26 27 9 20 18 19 35 24
5 4 2 23 17 6 3 22 21 29 1 16 7 15 12 13 30 1...

output:

Yes
Yes
No
No
Yes
No
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #19:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

18
30 21 27 20 34 10 25 18 19 22 15 9 28 29 35 32 26 36
4 11 1 3 17 2 24 13 7 5 14 6 23 12 33 31 16 ...

output:

No
No
No
Yes
Yes
No
No
Yes
No
Yes

result:

ok 10 tokens

Test #20:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

18
20 30 27 36 21 12 31 19 24 35 23 32 18 25 26 34 14 33
1 16 6 17 11 10 15 5 9 7 3 4 2 22 8 29 13 2...

output:

Yes
No
Yes
No
No
No
No
No
Yes
Yes

result:

ok 10 tokens

Test #21:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

16
16 25 14 29 18 30 4 17 7 9 8 19 31 22 21 32
5 24 13 28 12 27 3 15 6 2 1 11 26 10 20 23
10
4 13
2 ...

output:

Yes
No
Yes
No
Yes
No
No
No
No
Yes

result:

ok 10 tokens

Test #22:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

18
4 26 11 5 27 13 19 24 35 29 31 34 32 18 16 7 36 14
1 9 8 3 25 12 10 22 33 28 30 23 21 17 15 6 20 ...

output:

No
No
Yes
No
No
No
Yes
Yes
Yes
No

result:

ok 10 tokens

Test #23:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

18
11 24 18 20 3 33 34 27 30 22 36 28 19 9 15 10 5 29
6 23 17 13 2 32 31 12 25 1 35 21 16 8 14 7 4 2...

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 tokens

Test #24:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

18
28 25 17 26 18 8 35 3 36 34 12 13 21 32 29 20 30 31
19 24 16 23 15 7 10 1 22 33 11 9 4 5 27 14 6 ...

output:

No
No
Yes
No
No
Yes
No
No
Yes
No

result:

ok 10 tokens

Test #25:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

18
20 30 36 22 23 24 35 18 11 14 27 8 9 15 28 34 32 33
3 17 6 21 4 19 13 2 1 12 26 5 7 10 25 31 29 1...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #26:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

18
21 23 29 27 36 4 32 18 34 35 11 33 26 7 14 31 5 15
13 22 9 19 17 3 24 16 10 28 8 30 25 6 12 20 1 ...

output:

Yes
No
Yes
No
No
Yes
No
No
No
Yes

result:

ok 10 tokens

Test #27:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

18
8 26 36 16 22 18 10 32 30 14 12 34 28 4 24 20 2 6
7 25 35 15 21 17 9 31 29 13 11 33 27 3 23 19 1 ...

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 tokens

Test #28:

score: 0
Accepted
time: 0ms
memory: 1184kb

input:

18
22 34 20 30 19 35 25 31 32 28 27 33 26 21 29 23 36 24
5 6 11 18 16 13 8 9 14 2 1 3 15 7 12 4 10 1...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #29:

score: 0
Accepted
time: 0ms
memory: 1188kb

input:

18
12 17 30 19 18 32 14 22 36 35 27 29 25 21 9 28 16 20
5 1 26 10 3 31 13 6 34 33 11 2 23 4 8 24 15 ...

output:

Yes
No
No
No
No
Yes
No
No
No
No

result:

ok 10 tokens

Subtask #3:

score: 10
Accepted

Test #30:

score: 10
Accepted
time: 23ms
memory: 4864kb

input:

100000
200000 87337 190412 58171 10676 178924 155670 153538 106523 166320 196463 174807 19706 66971 ...

output:

Yes

result:

ok "Yes"

Test #31:

score: 0
Accepted
time: 18ms
memory: 4868kb

input:

99996
199992 55108 192122 156535 96703 158022 98612 154080 174501 80333 191718 138961 171355 154101 ...

output:

Yes

result:

ok "Yes"

Test #32:

score: 0
Accepted
time: 18ms
memory: 4868kb

input:

99999
199997 170879 161773 28645 163801 191566 171319 165453 53288 132456 157500 91941 146443 170074...

output:

Yes

result:

ok "Yes"

Test #33:

score: 0
Accepted
time: 15ms
memory: 4864kb

input:

99998
199995 171377 133250 170806 197343 162890 176641 198229 156952 106802 148078 134198 38360 1825...

output:

Yes

result:

ok "Yes"

Test #34:

score: 0
Accepted
time: 19ms
memory: 4864kb

input:

99994
199986 176184 128449 165655 180411 108099 175456 183507 96091 70117 144956 115377 154518 16049...

output:

Yes

result:

ok "Yes"

Test #35:

score: 0
Accepted
time: 23ms
memory: 4864kb

input:

99992
199982 94622 159310 166234 105469 44414 52091 123694 172916 179711 149323 115375 166040 92513 ...

output:

Yes

result:

ok "Yes"

Test #36:

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

input:

99994
199986 172588 101761 173680 154796 47906 165246 155807 142583 82053 124298 185751 146473 15284...

output:

No

result:

ok "No"

Test #37:

score: 0
Accepted
time: 21ms
memory: 4864kb

input:

99992
199982 109852 155026 157923 110059 91615 184436 197597 189940 165799 197946 168174 61274 18282...

output:

No

result:

ok "No"

Test #38:

score: 0
Accepted
time: 17ms
memory: 4868kb

input:

100000
199999 74639 195073 197398 179979 168474 145783 79979 159184 131687 174609 183930 160341 6842...

output:

Yes

result:

ok "Yes"

Subtask #4:

score: 10
Accepted

Test #39:

score: 10
Accepted
time: 20ms
memory: 4192kb

input:

74998
147369 94378 68913 123990 65257 88482 116281 130255 78568 141536 99818 113372 26849 44703 9508...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #40:

score: 0
Accepted
time: 33ms
memory: 4632kb

input:

100000
170854 85803 190478 195356 68149 101079 160091 179386 130394 139476 179555 126978 167547 7206...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #41:

score: 0
Accepted
time: 12ms
memory: 3328kb

input:

72263
130381 105716 139143 33477 86587 120207 73233 38155 92520 125495 23580 69974 121855 74665 1378...

output:

Yes
Yes
Yes
No
No
No
No
Yes
Yes
No

result:

ok 10 tokens

Test #42:

score: 0
Accepted
time: 22ms
memory: 4892kb

input:

100000
126626 150000 164533 93954 84178 127720 196307 191298 197000 58182 74847 177055 162414 81634 ...

output:

Yes
No
No
Yes
No
Yes
No
No
Yes
Yes

result:

ok 10 tokens

Test #43:

score: 0
Accepted
time: 49ms
memory: 5916kb

input:

98148
12647 155973 20767 36805 168027 146372 113253 66852 57625 1895 12580 165096 49832 70925 51643 ...

output:

Yes
No
No
Yes
No
No
No
No
No
No

result:

ok 10 tokens

Test #44:

score: 0
Accepted
time: 39ms
memory: 5948kb

input:

100000
10705 194107 21546 73701 152844 24382 42696 113958 60425 157337 37450 71952 62746 111551 1990...

output:

Yes
No
No
No
Yes
No
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #45:

score: 0
Accepted
time: 6ms
memory: 2520kb

input:

74884
106721 73638 67742 96410 111958 112231 35979 93104 109910 105533 125985 31820 90312 4917 46772...

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 tokens

Test #46:

score: 0
Accepted
time: 10ms
memory: 3448kb

input:

100000
194884 180232 99694 108507 186527 179325 154704 107083 14761 84155 140296 122106 99807 153759...

output:

Yes
No
No
No
No
No
No
No
Yes
No

result:

ok 10 tokens

Test #47:

score: 0
Accepted
time: 103ms
memory: 6480kb

input:

100000
48901 66438 27493 126347 130802 155756 127723 92218 110921 137983 87294 436 109907 103035 995...

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 tokens

Test #48:

score: 0
Accepted
time: 113ms
memory: 6476kb

input:

100000
178066 2105 144975 117797 157700 173597 18760 176834 114946 88498 166855 141665 106055 149341...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #49:

score: 0
Accepted
time: 64ms
memory: 6216kb

input:

100000
94066 77176 193622 73714 97624 79426 94370 176580 157580 141690 66586 8788 64196 100696 26030...

output:

No
No
No
No
No
No
No
No
No
No

result:

ok 10 tokens

Test #50:

score: 0
Accepted
time: 55ms
memory: 5948kb

input:

100000
105814 136154 194761 156342 191016 193768 121961 116018 128308 130066 179571 110568 126164 18...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 10 tokens

Test #51:

score: 0
Accepted
time: 49ms
memory: 4880kb

input:

100000
34427 128914 170520 39932 27524 58354 158017 146548 155397 2898 64206 3208 72908 110224 19313...

output:

No
No
No
Yes
No
No
No
No
No
Yes

result:

ok 10 tokens

Subtask #5:

score: 0
Wrong Answer

Test #52:

score: 0
Wrong Answer
time: 35ms
memory: 2404kb

input:

71726
4 5 7 10 11 17 20 24 26 27 28 29 31 35 36 38 40 42 44 46 48 50 51 52 55 56 57 59 61 62 66 68 6...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

wrong answer 1st words differ - expected: 'Yes', found: 'No'

Subtask #6:

score: 0
Time Limit Exceeded

Test #63:

score: 0
Time Limit Exceeded

input:

82281
1042 1077 1434 1646 1653 1686 1695 1709 1890 1994 2024 2035 2062 2072 2124 2212 2220 2235 2333...

output:

result:

Subtask #7:

score: 0
Time Limit Exceeded

Test #78:

score: 0
Time Limit Exceeded

input:

82558
126512 86112 114997 72735 152982 158440 165082 140323 163880 158215 70769 134792 94132 158947 ...

output:

result:

Subtask #8:

score: 0
Time Limit Exceeded

Test #88:

score: 0
Time Limit Exceeded

input:

493564
729874 763930 874124 652080 923918 396618 625421 743552 914276 948530 741356 314261 268607 96...

output:

result:

中文 English

Server time: 2025-03-19 22:53:10 | 开源项目