NOI.AC

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#212295	#3814. T4	drdilyor	40	659ms	6276kb	C++11	1.3kb	2024-10-13 18:09:32	2024-10-13 19:39:17

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];
signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	int q=read();
	while(q--){
		int l=read(),r=read();
		//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

Source code, Language: C++11

Details

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

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 0ms

memory: 1180kb

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

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

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

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

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

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

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

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: 0ms

memory: 1176kb

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

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

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

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

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

input:

output:

Yes

result:

ok "Yes"

Test #15:

score: 0

Accepted

time: 0ms

memory: 1172kb

input:

output:

No

result:

ok "No"

Test #16:

score: 0

Accepted

time: 0ms

memory: 1172kb

input:

output:

Yes

result:

ok "Yes"

Subtask #2:

score: 10

Accepted

Test #17:

score: 10

Accepted

time: 0ms

memory: 1176kb

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

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

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

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

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

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

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

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

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

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

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

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

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: 13ms

memory: 4668kb

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

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: 17ms

memory: 4664kb

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: 20ms

memory: 4664kb

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: 14ms

memory: 4660kb

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: 18ms

memory: 4664kb

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: 17ms

memory: 4664kb

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: 22ms

memory: 4664kb

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: 15ms

memory: 4668kb

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: 23ms

memory: 4040kb

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: 19ms

memory: 4428kb

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: 15ms

memory: 3180kb

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: 20ms

memory: 4696kb

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: 37ms

memory: 5716kb

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: 33ms

memory: 5748kb

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

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: 9ms

memory: 3248kb

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: 98ms

memory: 6276kb

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: 105ms

memory: 6276kb

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: 53ms

memory: 6012kb

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: 48ms

memory: 5748kb

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: 39ms

memory: 4680kb

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

Time Limit Exceeded

Test #52:

score: 0

Time Limit Exceeded

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:

Yes
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Y...

result:

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...