QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704351#196. ColorsTheZone100 ✓421ms54340kbC++2010.0kb2024-11-02 19:49:392024-11-02 19:49:39

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 19:49:39]
  • 评测
  • 测评结果：100
  • 用时：421ms
  • 内存：54340kb
查看
  • [2024-11-02 19:49:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
const int N=1.5e5;
int n,m;
vector<int> e[N+5];
int a[N+5],b[N+5];
vector<int> pa[N+5],pb[N+5];
bool ok[N+5],in[N+5];
struct Uni{
	int x,sz;
	Uni(int x=0,int sz=0):x(x),sz(sz){}
}f[N+5];
struct oper{
	int u,v;
	oper(int u=0,int v=0):u(u),v(v){}
};
vector<oper> op;
int find(int x){
	while(f[x].x!=x) x=f[x].x;
	return x;
}
void merge(int u,int v){
	u=find(u); v=find(v);
	if(u==v) return;
	if(f[u].sz>f[v].sz) swap(u,v);
	op.pb(u,v);
	f[u].x=v; f[v].sz+=f[u].sz;
}
void back(int lst){
	while(op.size()>lst){
		oper t=op.back(); op.pop_back();
		f[t.u].x=t.u; f[t.v].sz-=f[t.u].sz;
	}
}
vector<int> ver[N*4+5];
bool ans;
void pushv(int l,int r,int u,int id){
	if(b[u]<=l&&a[u]>=r){
		ver[id].pb(u); return;
	}
	int mid=l+r>>1;
	if(b[u]<=mid) pushv(l,mid,u,id<<1);
	if(a[u]>mid) pushv(mid+1,r,u,id<<1|1);
}
void work(int l,int r,int id){
	int lst=op.size();
	for(auto u:ver[id]){
		in[u]=1;
		for(auto v:e[u])
			if(in[v]) merge(u,v);
	}
	if(l==r){
		for(auto i:pa[l]) ok[find(i)]=1;
		for(auto i:pb[l]) ans&=ok[find(i)];
		for(auto i:pa[l]) ok[find(i)]=0;
	}
	else{
		int mid=l+r>>1;
		work(l,mid,id<<1);
		work(mid+1,r,id<<1|1);
	}
	back(lst);
	for(auto u:ver[id]) in[u]=0;
	ver[id].clear(); ver[id].shrink_to_fit();
}
void solve(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pa[a[i]].pb(i);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		pb[b[i]].pb(i);
	}
	for(int i=1,u,v;i<=m;i++){
		scanf("%d %d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		if(a[i]<b[i]){
			puts("0"); return;
		}
	ans=1;
	for(int i=1;i<=n;i++) f[i]=Uni(i,1);
	for(int i=1;i<=n;i++) pushv(1,n,i,1);
	work(1,n,1);
	puts(ans?"1":"0");
}
int main(){
	int t; scanf("%d",&t);
	while(t--){
		solve();
		for(int i=1;i<=n;i++){
			pa[i].clear(); pa[i].shrink_to_fit();
			pb[i].clear(); pb[i].shrink_to_fit();
			e[i].clear(); e[i].shrink_to_fit();
		}
	}
	return 0;
}
/*#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
const int N=1.5e5;
int n,m;
vector<int> e[N+5];
int a[N+5],b[N+5];
vector<int> pa[N+5],pb[N+5];
bool ok[N+5],in[N+5];
struct Uni{
	int x,sz;
	Uni(int x=0,int sz=0):x(x),sz(sz){}
}f[N+5];
struct oper{
	int u,v;
	oper(int u=0,int v=0):u(u),v(v){}
};
vector<oper> op;
int find(int x){
	while(f[x].x!=x) x=f[x].x;
	return x;
}
void merge(int u,int v){
	u=find(u); v=find(v);
	if(u==v) return;
	if(f[u].sz>f[v].sz) swap(u,v);
	op.pb(u,v);
	f[u].x=v; f[v].sz+=f[u].sz;
}
void back(int lst){
	while(op.size()>lst){
		oper t=op.back(); op.pop_back();
		f[t.u].x=t.u; f[t.v].sz-=f[t.u].sz;
	}
}
vector<int> ver[N*4+5];
bool ans;
void pushv(int l,int r,int u,int id){
	if(b[u]<=l&&a[u]>=r){
		ver[id].pb(u); return;
	}
	int mid=l+r>>1;
	if(b[u]<=mid) pushv(l,mid,u,id<<1);
	if(a[u]>mid) pushv(mid+1,r,u,id<<1|1);
}
void work(int l,int r,int id){
	int lst=op.size();
	for(auto u:ver[id]){
		in[u]=1;
		for(auto v:e[u])
			if(in[v]) merge(u,v);
	}
	if(l==r){
		for(auto i:pa[l]) ok[find(i)]=1;
		for(auto i:pb[l]) ans&=ok[find(i)];
		for(auto i:pa[l]) ok[find(i)]=0;
	}
	else{
		int mid=l+r>>1;
		work(l,mid,id<<1);
		work(mid+1,r,id<<1|1);
	}
	back(lst);
	for(auto u:ver[id]) in[u]=0;
	ver[id].clear(); ver[id].shrink_to_fit();
}
void solve(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pa[a[i]].pb(i);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		pb[b[i]].pb(i);
	}
	for(int i=1,u,v;i<=m;i++){
		scanf("%d %d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		if(a[i]<b[i]){
			puts("0"); return;
		}
	ans=1;
	for(int i=1;i<=n;i++) f[i]=Uni(i,1);
	for(int i=1;i<=n;i++) pushv(1,n,i,1);
	work(1,n,1);
	puts(ans?"1":"0");
}
int main(){
	int t; scanf("%d",&t);
	while(t--){
		solve();
		for(int i=1;i<=n;i++){
			pa[i].clear(); pa[i].shrink_to_fit();
			pb[i].clear(); pb[i].shrink_to_fit();
			e[i].clear(); e[i].shrink_to_fit();
		}
	}
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
const int N=1.5e5;
int n,m;
vector<int> e[N+5];
int a[N+5],b[N+5];
vector<int> pa[N+5],pb[N+5];
bool ok[N+5],in[N+5];
struct Uni{
	int x,sz;
	Uni(int x=0,int sz=0):x(x),sz(sz){}
}f[N+5];
struct oper{
	int u,v;
	oper(int u=0,int v=0):u(u),v(v){}
};
vector<oper> op;
int find(int x){
	while(f[x].x!=x) x=f[x].x;
	return x;
}
void merge(int u,int v){
	u=find(u); v=find(v);
	if(u==v) return;
	if(f[u].sz>f[v].sz) swap(u,v);
	op.pb(u,v);
	f[u].x=v; f[v].sz+=f[u].sz;
}
void back(int lst){
	while(op.size()>lst){
		oper t=op.back(); op.pop_back();
		f[t.u].x=t.u; f[t.v].sz-=f[t.u].sz;
	}
}
vector<int> ver[N*4+5];
bool ans;
void pushv(int l,int r,int u,int id){
	if(b[u]<=l&&a[u]>=r){
		ver[id].pb(u); return;
	}
	int mid=l+r>>1;
	if(b[u]<=mid) pushv(l,mid,u,id<<1);
	if(a[u]>mid) pushv(mid+1,r,u,id<<1|1);
}
void work(int l,int r,int id){
	int lst=op.size();
	for(auto u:ver[id]){
		in[u]=1;
		for(auto v:e[u])
			if(in[v]) merge(u,v);
	}
	if(l==r){
		for(auto i:pa[l]) ok[find(i)]=1;
		for(auto i:pb[l]) ans&=ok[find(i)];
		for(auto i:pa[l]) ok[find(i)]=0;
	}
	else{
		int mid=l+r>>1;
		work(l,mid,id<<1);
		work(mid+1,r,id<<1|1);
	}
	back(lst);
	for(auto u:ver[id]) in[u]=0;
	ver[id].clear(); ver[id].shrink_to_fit();
}
void solve(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pa[a[i]].pb(i);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		pb[b[i]].pb(i);
	}
	for(int i=1,u,v;i<=m;i++){
		scanf("%d %d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		if(a[i]<b[i]){
			puts("0"); return;
		}
	ans=1;
	for(int i=1;i<=n;i++) f[i]=Uni(i,1);
	for(int i=1;i<=n;i++) pushv(1,n,i,1);
	work(1,n,1);
	puts(ans?"1":"0");
}
int main(){
	int t; scanf("%d",&t);
	while(t--){
		solve();
		for(int i=1;i<=n;i++){
			pa[i].clear(); pa[i].shrink_to_fit();
			pb[i].clear(); pb[i].shrink_to_fit();
			e[i].clear(); e[i].shrink_to_fit();
		}
	}
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
const int N=1.5e5;
int n,m;
vector<int> e[N+5];
int a[N+5],b[N+5];
vector<int> pa[N+5],pb[N+5];
bool ok[N+5],in[N+5];
struct Uni{
	int x,sz;
	Uni(int x=0,int sz=0):x(x),sz(sz){}
}f[N+5];
struct oper{
	int u,v;
	oper(int u=0,int v=0):u(u),v(v){}
};
vector<oper> op;
int find(int x){
	while(f[x].x!=x) x=f[x].x;
	return x;
}
void merge(int u,int v){
	u=find(u); v=find(v);
	if(u==v) return;
	if(f[u].sz>f[v].sz) swap(u,v);
	op.pb(u,v);
	f[u].x=v; f[v].sz+=f[u].sz;
}
void back(int lst){
	while(op.size()>lst){
		oper t=op.back(); op.pop_back();
		f[t.u].x=t.u; f[t.v].sz-=f[t.u].sz;
	}
}
vector<int> ver[N*4+5];
bool ans;
void pushv(int l,int r,int u,int id){
	if(b[u]<=l&&a[u]>=r){
		ver[id].pb(u); return;
	}
	int mid=l+r>>1;
	if(b[u]<=mid) pushv(l,mid,u,id<<1);
	if(a[u]>mid) pushv(mid+1,r,u,id<<1|1);
}
void work(int l,int r,int id){
	int lst=op.size();
	for(auto u:ver[id]){
		in[u]=1;
		for(auto v:e[u])
			if(in[v]) merge(u,v);
	}
	if(l==r){
		for(auto i:pa[l]) ok[find(i)]=1;
		for(auto i:pb[l]) ans&=ok[find(i)];
		for(auto i:pa[l]) ok[find(i)]=0;
	}
	else{
		int mid=l+r>>1;
		work(l,mid,id<<1);
		work(mid+1,r,id<<1|1);
	}
	back(lst);
	for(auto u:ver[id]) in[u]=0;
	ver[id].clear(); ver[id].shrink_to_fit();
}
void solve(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pa[a[i]].pb(i);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		pb[b[i]].pb(i);
	}
	for(int i=1,u,v;i<=m;i++){
		scanf("%d %d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		if(a[i]<b[i]){
			puts("0"); return;
		}
	ans=1;
	for(int i=1;i<=n;i++) f[i]=Uni(i,1);
	for(int i=1;i<=n;i++) pushv(1,n,i,1);
	work(1,n,1);
	puts(ans?"1":"0");
}
int main(){
	int t; scanf("%d",&t);
	while(t--){
		solve();
		for(int i=1;i<=n;i++){
			pa[i].clear(); pa[i].shrink_to_fit();
			pb[i].clear(); pb[i].shrink_to_fit();
			e[i].clear(); e[i].shrink_to_fit();
		}
	}
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
const int N=1.5e5;
int n,m;
vector<int> e[N+5];
int a[N+5],b[N+5];
vector<int> pa[N+5],pb[N+5];
bool ok[N+5],in[N+5];
struct Uni{
	int x,sz;
	Uni(int x=0,int sz=0):x(x),sz(sz){}
}f[N+5];
struct oper{
	int u,v;
	oper(int u=0,int v=0):u(u),v(v){}
};
vector<oper> op;
int find(int x){
	while(f[x].x!=x) x=f[x].x;
	return x;
}
void merge(int u,int v){
	u=find(u); v=find(v);
	if(u==v) return;
	if(f[u].sz>f[v].sz) swap(u,v);
	op.pb(u,v);
	f[u].x=v; f[v].sz+=f[u].sz;
}
void back(int lst){
	while(op.size()>lst){
		oper t=op.back(); op.pop_back();
		f[t.u].x=t.u; f[t.v].sz-=f[t.u].sz;
	}
}
vector<int> ver[N*4+5];
bool ans;
void pushv(int l,int r,int u,int id){
	if(b[u]<=l&&a[u]>=r){
		ver[id].pb(u); return;
	}
	int mid=l+r>>1;
	if(b[u]<=mid) pushv(l,mid,u,id<<1);
	if(a[u]>mid) pushv(mid+1,r,u,id<<1|1);
}
void work(int l,int r,int id){
	int lst=op.size();
	for(auto u:ver[id]){
		in[u]=1;
		for(auto v:e[u])
			if(in[v]) merge(u,v);
	}
	if(l==r){
		for(auto i:pa[l]) ok[find(i)]=1;
		for(auto i:pb[l]) ans&=ok[find(i)];
		for(auto i:pa[l]) ok[find(i)]=0;
	}
	else{
		int mid=l+r>>1;
		work(l,mid,id<<1);
		work(mid+1,r,id<<1|1);
	}
	back(lst);
	for(auto u:ver[id]) in[u]=0;
	ver[id].clear(); ver[id].shrink_to_fit();
}
void solve(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pa[a[i]].pb(i);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		pb[b[i]].pb(i);
	}
	for(int i=1,u,v;i<=m;i++){
		scanf("%d %d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		if(a[i]<b[i]){
			puts("0"); return;
		}
	ans=1;
	for(int i=1;i<=n;i++) f[i]=Uni(i,1);
	for(int i=1;i<=n;i++) pushv(1,n,i,1);
	work(1,n,1);
	puts(ans?"1":"0");
}
int main(){
	int t; scanf("%d",&t);
	while(t--){
		solve();
		for(int i=1;i<=n;i++){
			pa[i].clear(); pa[i].shrink_to_fit();
			pb[i].clear(); pb[i].shrink_to_fit();
			e[i].clear(); e[i].shrink_to_fit();
		}
	}
	return 0;
}
*/
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 54ms
memory: 9836kb

input:

5677
12 11
2 4 3 2 7 9 3 1 10 9 4 10
1 1 1 1 1 1 1 1 1 9 1 1
12 11
12 5
1 12
12 10
8 12
2 12
7 12
12 6
12 4
3 12
9 12
15 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 1 6 7 8 9 10 11 9 13 9 6
1 15
15 11
15 7
15 10
15 8
12 15
15 14
15 5
9 15
2 15
6 15
4 15
15 3
13 15
1 0
1
1
41 40
17 17 4 34 31 34 2...

output:

1
0
1
0
0
1
0
0
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
0
0
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
0
0
0
0
0
1
1
0
1
0
0
0
1
0
0
1
1
1
1
1
0
1
1
1
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
0
0
1
1
1
0
0
0
1
1
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
1
0
0
0
1
0
1
1
1
1
...

result:

ok 5677 lines

Test #2:

score: 15
Accepted
time: 22ms
memory: 7800kb

input:

500
108 107
66 41 19 27 2 37 104 73 29 96 95 97 47 33 104 91 2 81 61 95 18 14 49 107 16 21 62 96 51 104 59 82 86 89 87 68 16 41 24 33 30 66 57 5 97 18 29 100 77 29 22 6 47 55 63 81 40 83 18 74 76 17 66 85 15 10 105 85 64 6 27 21 89 53 82 29 64 3 69 37 22 2 25 81 102 84 91 7 22 58 79 69 18 30 18 44 5...

output:

0
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
1
1
1
1
0
1
1
1
0
1
0
1
1
0
1
1
0
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
0
1
0
1
1
1
0
1
1
1
0
0
0
1
1
1
1
1
1
1
0
0
0
1
1
1
...

result:

ok 500 lines

Test #3:

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

input:

4
1081 1080
9 193 484 833 1071 513 990 480 1060 885 857 130 140 200 134 800 451 1079 770 146 353 520 1058 355 91 857 634 2 189 650 420 770 935 665 343 619 257 986 902 269 578 72 596 780 850 343 961 850 1015 345 543 939 14 928 412 1039 548 387 554 1021 190 50 259 1045 175 277 531 61 887 709 626 904 3...

output:

0
1
0
1

result:

ok 4 lines

Subtask #2:

score: 7
Accepted

Test #4:

score: 7
Accepted
time: 36ms
memory: 7872kb

input:

691
13 78
1 2 3 4 5 6 7 8 9 10 11 12 13
1 1 1 1 1 1 1 1 1 1 1 12 1
13 7
11 5
1 12
7 3
1 7
13 4
7 9
9 1
10 1
2 1
8 1
2 9
9 12
7 11
10 7
10 4
12 5
2 7
3 2
4 3
1 6
12 6
5 7
10 8
3 8
5 4
3 13
11 2
12 2
12 4
5 13
6 2
9 6
5 9
8 7
9 10
3 5
8 13
12 13
6 11
3 12
10 13
3 1
12 10
8 12
1 5
6 13
8 9
2 10
6 4
11 ...

output:

1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 691 lines

Subtask #3:

score: 8
Accepted

Test #5:

score: 8
Accepted
time: 67ms
memory: 9920kb

input:

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

output:

0
0
0
1
0
1
0
1
0
1
0
0
1
1
0
1
1
0
1
1
1
0
0
1
0
1
1
0
0
1
1
1
1
0
0
1
0
1
1
0
1
1
1
1
0
0
0
0
1
0
0
1
0
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
1
0
1
1
1
0
1
1
1
1
0
1
1
0
0
1
0
0
1
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
0
0
1
0
0
0
1
0
1
0
1
0
1
1
0
0
0
1
0
1
0
1
1
1
1
1
1
1
0
0
1
0
1
1
0
0
1
0
1
0
0
0
1
1
0
1
1
0
...

result:

ok 5802 lines

Test #6:

score: 8
Accepted
time: 23ms
memory: 7804kb

input:

490
88 87
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
1 2 3 4 5 6 7 5 9 10 11 12 13 14 15...

output:

1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
1
0
0
0
1
1
0
0
0
1
0
0
1
1
0
1
0
0
1
0
1
0
1
1
1
1
1
1
0
0
0
0
1
0
1
0
1
1
1
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
0
0
1
1
0
1
1
0
0
1
0
0
0
1
0
0
0
1
1
1
1
0
1
1
0
1
1
0
1
0
1
0
1
1
0
1
0
0
0
0
0
0
1
0
0
0
0
1
1
0
1
1
0
1
0
0
0
1
0
0
1
1
0
...

result:

ok 490 lines

Test #7:

score: 8
Accepted
time: 0ms
memory: 8220kb

input:

5
988 987
693 726 945 360 204 520 461 262 507 846 474 941 531 413 900 354 943 266 38 794 719 145 377 972 562 503 126 224 661 937 388 558 858 211 460 971 697 386 712 312 130 682 673 740 921 608 909 815 641 5 657 634 758 302 839 236 344 650 370 64 689 915 685 500 810 110 400 292 187 190 35 397 338 28 ...

output:

0
1
0
0
1

result:

ok 5 lines

Subtask #4:

score: 15
Accepted

Dependency #3:

100%
Accepted

Test #8:

score: 15
Accepted
time: 141ms
memory: 7824kb

input:

7394
58 57
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
1 2 1 2 1 1 7 8 9 8 7 8 1 8 8 1 1 7 8 7 8 9 1 8 7 8 2 9 9 8 1 1 7 8 9 8 8 1 8 1 9 8 1 8 7 1 1 7 7 1 8 8 8 7 9 1 7 7
19 26
56...

output:

0
1
1
1
0
1
0
1
1
1
0
0
1
1
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
0
1
1
1
1
1
1
0
0
0
0
0
1
0
1
0
1
0
1
1
0
1
1
0
1
1
1
0
0
1
1
0
0
0
1
1
1
0
0
0
1
1
0
1
1
0
0
1
0
1
1
1
1
1
0
1
0
1
1
0
0
0
0
0
1
0
0
0
1
0
1
1
0
1
1
1
1
1
0
1
1
0
1
1
0
1
0
1
0
1
1
0
0
0
0
0
1
1
1
1
1
0
0
0
1
1
1
0
1
0
0
0
0
0
1
1
0
...

result:

ok 7394 lines

Test #9:

score: 15
Accepted
time: 324ms
memory: 24308kb

input:

8
36667 36666
26752 5646 31894 33101 32009 5326 1563 21117 29875 16461 30042 22272 32169 32635 14172 15236 34013 31805 29933 6239 8378 5586 35279 32503 18954 22052 14108 36197 1505 20877 2055 9004 30686 30518 8766 20922 19896 13260 33824 21491 24759 18970 22654 19230 28625 17988 3502 25785 4707 3595...

output:

0
1
1
1
0
0
1
1

result:

ok 8 lines

Test #10:

score: 15
Accepted
time: 421ms
memory: 54340kb

input:

2
149410 149409
77343 11912 127782 581 133148 96791 81482 69735 54805 55931 80918 107921 18353 59874 13673 120762 33857 113506 54190 48029 134682 144346 103308 62922 11966 27765 30197 125918 144328 114911 42333 43458 48317 59107 125024 132850 135737 74449 28347 141056 148239 120136 53291 112615 1704...

output:

0
1

result:

ok 2 lines

Subtask #5:

score: 7
Accepted

Test #11:

score: 7
Accepted
time: 66ms
memory: 9860kb

input:

5787
45 44
36 42 10 19 35 11 10 8 28 20 11 21 20 19 32 25 20 32 12 30 38 43 23 17 22 45 6 30 23 19 5 39 11 6 15 20 39 17 24 32 19 29 7 4 1
20 42 10 6 6 1 10 8 1 1 11 21 20 19 32 1 6 1 12 1 6 43 23 17 22 45 6 6 23 19 5 39 11 6 15 20 39 1 24 32 19 1 6 1 1
10 19
10 43
4 10
2 10
10 5
23 10
10 36
40 10
1...

output:

1
0
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
0
1
0
1
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
1
0
0
1
1
1
1
1
0
0
1
1
1
1
0
1
1
0
1
0
0
0
0
0
0
1
1
1
0
1
1
0
0
1
1
1
1
0
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
0
1
1
...

result:

ok 5787 lines

Test #12:

score: 7
Accepted
time: 23ms
memory: 9820kb

input:

492
102 101
81 16 7 78 31 88 9 82 20 61 23 5 4 89 74 31 75 55 9 90 57 95 70 28 15 87 55 36 7 77 89 52 81 61 12 97 5 30 10 57 69 89 81 102 73 100 85 35 70 24 55 36 15 36 44 101 65 87 72 90 26 28 87 47 61 96 89 62 82 96 5 79 33 84 10 91 98 85 8 28 36 82 80 62 47 87 5 4 80 15 14 45 20 94 12 47 100 34 3...

output:

0
1
0
0
1
0
0
1
1
1
0
1
1
1
1
0
0
1
1
1
1
1
0
1
0
0
1
1
1
0
1
0
1
1
1
0
1
1
1
1
0
0
1
1
1
0
1
0
0
0
1
1
0
0
0
0
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
1
0
1
0
1
0
0
1
1
1
1
0
0
1
1
1
0
0
0
0
1
0
1
0
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
1
0
1
1
1
0
0
1
0
1
1
1
1
0
1
1
1
1
1
0
0
0
0
1
...

result:

ok 492 lines

Test #13:

score: 7
Accepted
time: 6ms
memory: 10180kb

input:

5
1097 1096
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

0
1
0
0
1

result:

ok 5 lines

Subtask #6:

score: 16
Accepted

Test #14:

score: 16
Accepted
time: 130ms
memory: 9780kb

input:

7378
53 52
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
1 2 2 4 5 6 7 8 5 10 11 12 13 14 10 16 17 18 19 20 21 22 23 24 5 4 25 12 10 17 14 10 15 34 35 36 37 25 1 40 20 25 43 44 13 46 6 2 49 16 16 ...

output:

0
0
0
0
1
0
1
1
0
0
1
0
1
1
0
1
1
0
1
1
0
1
0
0
0
1
0
0
0
1
0
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
0
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
0
1
1
1
1
0
1
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
0
1
1
1
1
0
1
...

result:

ok 7378 lines

Test #15:

score: 16
Accepted
time: 291ms
memory: 23076kb

input:

7
30020 30019
4663 29166 3048 22809 1613 2217 18027 16429 29362 2541 9513 16975 5216 7864 4760 29082 27342 18164 18080 6534 6688 20527 16062 15624 17708 22618 17001 1745 1979 26879 14339 452 10214 6019 21235 6785 1134 7138 4348 25360 4934 17993 11977 12703 5489 5381 22044 20046 12570 16709 776 18814...

output:

1
1
0
0
0
0
1

result:

ok 7 lines

Test #16:

score: 16
Accepted
time: 304ms
memory: 53492kb

input:

2
141386 141385
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
1

result:

ok 2 lines

Subtask #7:

score: 10
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #17:

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

input:

561
47 269
32 23 3 1 6 42 41 6 11 44 26 29 31 46 28 34 23 29 38 37 42 45 14 26 11 38 17 47 20 47 38 30 3 1 28 1 18 31 47 31 7 11 17 46 7 44 45
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
37 16
5 3
11 1
16 21
37 17
30 45
12 40
29 40
13 21
10 32
47 46
...

output:

1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
...

result:

ok 561 lines

Test #18:

score: 10
Accepted
time: 3ms
memory: 7880kb

input:

38
84 443
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
0
0
1
1
1
0
1
1
1
0
1
1
1

result:

ok 38 lines

Test #19:

score: 10
Accepted
time: 6ms
memory: 12000kb

input:

10
387 862
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

1
1
0
1
1
0
1
0
1
0

result:

ok 10 lines

Subtask #8:

score: 22
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Test #20:

score: 22
Accepted
time: 62ms
memory: 9868kb

input:

743
75 2219
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1
1
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 743 lines

Test #21:

score: 22
Accepted
time: 271ms
memory: 27936kb

input:

7
20212 34695
2867 16374 14985 1660 3631 16550 6982 17262 15433 5839 13232 144 8972 2496 411 12656 17697 3620 12755 8713 3387 14018 19229 2998 8448 13002 10655 12016 9353 5275 15416 15299 11634 3895 17985 18653 3748 3522 4953 18971 5922 687 7051 13554 3300 10954 7178 20156 7795 11052 13508 3728 1966...

output:

1
0
1
1
1
0
0

result:

ok 7 lines

Test #22:

score: 22
Accepted
time: 399ms
memory: 53860kb

input:

2
134014 185683
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

0
1

result:

ok 2 lines
English 繁體中文 简体中文

伺服器時間: 2025-02-01 19:52:32 | 開源專案