QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#865268#9982. Staircase MuseumyhdddWA 128ms12584kbC++201.6kb2025-01-21 16:21:472025-01-21 16:21:49

Judging History

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

  • [2025-01-21 16:21:49]
  • 评测
  • 测评结果:WA
  • 用时:128ms
  • 内存:12584kb
  • [2025-01-21 16:21:47]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int maxn=200010;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n,l[maxn],r[maxn],m;
pii a[maxn];
int lsh[maxn],len;
#define lb(x) (x&(-x))
int tree[maxn];
void upd(int x,int w){
	while(x<=len)tree[x]=max(tree[x],w),x+=lb(x);
}
int que(int x){
	int res=0;
	while(x)res=max(res,tree[x]),x-=lb(x);
	return res;
}
void work(){
	n=read();int ans=0;
	a[m=1]={1,0};
	for(int i=1;i<=n;i++){
		l[i]=(read()-1)*2,r[i]=read()*2;
	}
	for(int i=1;i<n;i++){
		if(r[i+1]>r[i])a[++m]={2*i,r[i]+1};
		if(l[i+1]>l[i])a[++m]={2*i+1,l[i+1]};
	}
	sort(a+1,a+m+1);
	// for(int i=1;i<=m;i++)cout<<a[i].fi<<" "<<a[i].se<<"\n";
	len=0;for(int i=1;i<=m;i++)lsh[++len]=a[i].se;
	sort(lsh+1,lsh+len+1),len=unique(lsh+1,lsh+len+1)-lsh-1;
	for(int i=1;i<=m;i++)a[i].se=lower_bound(lsh+1,lsh+len+1,a[i].se)-lsh;
	for(int i=1;i<=len;i++)tree[i]=0;
	for(int i=1;i<=m;i++){
		int dp=que(a[i].se-1)+1;
		upd(a[i].se,dp);
		ans=max(ans,dp);
	}
	printf("%lld\n",ans);
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=read();
	while(T--)work();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 12108kb

input:

4
3
1 2
1 3
1 3
3
1 2
2 3
3 3
3
1 1
1 3
3 3
4
1 2
2 3
3 4
4 5

output:

2
3
3
4

result:

ok 4 number(s): "2 3 3 4"

Test #2:

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

input:

1
1
1 1000000000

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 2ms
memory: 8012kb

input:

9653
1
1 1
2
1 1
1 1
3
1 1
1 1
1 1
4
1 1
1 1
1 1
1 1
5
1 1
1 1
1 1
1 1
1 1
6
1 1
1 1
1 1
1 1
1 1
1 1
6
1 2
1 2
1 2
1 2
1 2
2 2
6
1 1
1 1
1 1
1 1
1 1
1 2
6
1 2
1 2
1 2
1 2
1 2
2 3
5
1 2
1 2
1 2
1 2
2 2
6
1 2
1 2
1 2
1 2
2 2
2 2
6
1 3
1 3
1 3
1 3
2 3
3 3
6
1 2
1 2
1 2
1 2
2 2
2 3
6
1 3
1 3
1 3
1 3
2 3...

output:

1
1
1
1
1
1
2
2
2
2
2
3
3
3
2
2
2
3
3
2
3
2
2
3
3
3
3
3
2
2
2
3
3
3
3
3
4
4
4
3
3
3
4
4
3
4
3
3
4
4
4
4
4
2
2
2
2
3
3
2
3
3
3
2
2
3
3
3
3
3
3
3
3
3
3
4
4
3
3
4
4
3
4
3
3
3
4
4
3
3
4
4
3
4
2
2
3
3
3
3
3
3
4
4
3
4
2
2
2
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
3
3
3
4
4
3
3
4
4
3
4
3
3
4
4
4
4
4
4
4
4
4
3
3
4
...

result:

ok 9653 numbers

Test #4:

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

input:

40000
7
1 1
1 1
1 1
1 1
1 1
1 1
1 1
7
1 2
1 2
1 2
1 2
1 2
1 2
2 2
7
1 1
1 1
1 1
1 1
1 1
1 1
1 2
7
1 2
1 2
1 2
1 2
1 2
1 2
2 3
7
1 2
1 2
1 2
1 2
1 2
2 2
2 2
7
1 3
1 3
1 3
1 3
1 3
2 3
3 3
7
1 2
1 2
1 2
1 2
1 2
2 2
2 3
7
1 3
1 3
1 3
1 3
1 3
2 3
3 4
7
1 1
1 1
1 1
1 1
1 1
1 2
1 2
7
1 2
1 2
1 2
1 2
1 2
1 ...

output:

1
2
2
2
2
3
3
3
2
2
3
3
2
3
2
3
3
3
3
3
2
3
3
3
3
4
4
4
3
3
4
4
3
4
3
4
4
4
4
4
2
2
3
3
2
3
3
3
2
3
3
3
3
3
3
3
3
3
4
4
3
3
4
4
3
4
3
3
4
4
3
3
4
4
3
4
2
3
3
3
3
3
4
4
3
4
2
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
3
3
4
4
3
3
4
4
3
4
3
4
4
4
4
4
4
4
4
4
3
4
4
4
3
4
4
4
4
4
2
3
3
3
3
4
4
4
3
3
4
4
3
4
3
4
4
4
...

result:

ok 40000 numbers

Test #5:

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

input:

35412
7
1 2
1 5
2 6
3 7
4 8
5 8
6 8
7
1 2
1 5
2 7
3 8
4 9
5 9
7 9
7
1 2
1 5
2 6
3 7
4 8
5 8
6 9
7
1 2
1 5
2 7
3 8
4 9
5 9
7 10
7
1 2
1 5
2 6
3 7
4 8
5 8
7 8
7
1 2
1 5
2 6
3 8
4 9
5 9
8 9
7
1 2
1 5
2 6
3 7
4 8
5 8
7 9
7
1 2
1 5
2 6
3 8
4 9
5 9
8 10
7
1 2
1 5
2 6
3 7
4 8
5 8
8 8
7
1 2
1 5
2 6
3 7
4 9
...

output:

6
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
6
7
7
6
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
6
7
7
6
7
4
5
5
5
...

result:

ok 35412 numbers

Test #6:

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

input:

62500
8
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
8
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 2
8
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 2
8
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 3
8
1 2
1 2
1 2
1 2
1 2
1 2
2 2
2 2
8
1 3
1 3
1 3
1 3
1 3
1 3
2 3
3 3
8
1 2
1 2
1 2
1 2
1 2
1 2
2 2
2 3
8
1 3
1 3
1 3
1 3
1 3
1 3
2 3
3 4
8
1 1
1 1
1 1
1 1
1 1
...

output:

1
2
2
2
2
3
3
3
2
2
3
3
2
3
2
3
3
3
3
3
2
3
3
3
3
4
4
4
3
3
4
4
3
4
3
4
4
4
4
4
2
2
3
3
2
3
3
3
2
3
3
3
3
3
3
3
3
3
4
4
3
3
4
4
3
4
3
3
4
4
3
3
4
4
3
4
2
3
3
3
3
3
4
4
3
4
2
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
3
3
4
4
3
3
4
4
3
4
3
4
4
4
4
4
4
4
4
4
3
4
4
4
3
4
4
4
4
4
2
3
3
3
3
4
4
4
3
3
4
4
3
4
3
4
4
4
...

result:

ok 62500 numbers

Test #7:

score: 0
Accepted
time: 20ms
memory: 12108kb

input:

62500
8
1 3
1 3
2 5
3 6
3 6
3 6
5 7
6 8
8
1 3
1 3
2 5
3 7
3 7
3 7
5 8
7 9
8
1 3
1 3
2 5
3 6
3 6
3 6
5 7
7 7
8
1 3
1 3
2 5
3 6
3 6
3 6
5 7
7 8
8
1 3
1 3
2 4
3 5
3 5
3 5
5 5
5 5
8
1 3
1 3
2 4
3 6
3 6
3 6
5 6
6 6
8
1 3
1 3
2 4
3 5
3 5
3 5
5 5
5 6
8
1 3
1 3
2 4
3 6
3 6
3 6
5 6
6 7
8
1 3
1 3
2 4
3 6
3 6
...

output:

5
5
5
5
4
5
5
5
4
5
5
5
4
5
5
5
5
5
4
5
5
5
5
5
4
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
5
5
6
6
5
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
4
4
5
5
4
4
5
5
4
4
5
5
4
5
5
5
4
5
...

result:

ok 62500 numbers

Test #8:

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

input:

62500
8
1 3
2 3
3 5
3 5
5 6
5 6
6 6
6 6
8
1 3
2 3
3 5
3 5
5 7
5 7
6 7
7 7
8
1 3
2 3
3 5
3 5
5 6
5 6
6 6
6 7
8
1 3
2 3
3 5
3 5
5 7
5 7
6 7
7 8
8
1 3
2 3
3 5
3 5
5 7
5 7
7 7
7 7
8
1 3
2 3
3 5
3 5
5 8
5 8
7 8
8 8
8
1 3
2 3
3 5
3 5
5 7
5 7
7 7
7 8
8
1 3
2 3
3 5
3 5
5 8
5 8
7 8
8 9
8
1 3
2 3
3 5
3 5
5 6
...

output:

5
6
6
6
5
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
6
7
6
7
7
7
7
7
7
7
7
7
6
7
7
7
6
7
7
7
6
7
7
7
7
7
6
7
7
7
7
7
5
5
6
6
5
5
6
6
5
6
6
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
6
7
7
6
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
7
7
6
6
...

result:

ok 62500 numbers

Test #9:

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

input:

62500
8
1 2
1 5
2 5
2 5
3 6
4 7
5 7
5 8
8
1 2
1 6
2 6
2 6
3 7
4 8
5 8
6 9
8
1 2
1 5
2 5
2 5
3 6
4 7
5 7
6 7
8
1 2
1 5
2 5
2 5
3 7
4 8
5 8
7 8
8
1 2
1 5
2 5
2 5
3 6
4 7
5 7
6 8
8
1 2
1 5
2 5
2 5
3 7
4 8
5 8
7 9
8
1 2
1 5
2 5
2 5
3 6
4 7
5 7
7 7
8
1 2
1 5
2 5
2 5
3 6
4 8
5 8
8 8
8
1 2
1 5
2 5
2 5
3 6
...

output:

6
6
6
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
5
5
6
6
5
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
6
6
4
5
5
5
5
6
6
6
5
5
6
6
5
6
5
6
6
6
6
6
4
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
5
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
6
6
...

result:

ok 62500 numbers

Test #10:

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

input:

62500
8
1 1
1 4
1 5
1 7
3 8
4 8
7 8
8 9
8
1 1
1 4
1 5
1 7
3 9
4 9
7 9
9 10
8
1 1
1 4
1 5
1 6
3 7
4 7
6 8
6 8
8
1 1
1 4
1 5
1 7
3 8
4 8
6 9
7 9
8
1 1
1 4
1 5
1 6
3 7
4 7
6 8
6 9
8
1 1
1 4
1 5
1 7
3 8
4 8
6 9
7 10
8
1 1
1 4
1 5
1 6
3 7
4 7
6 8
7 8
8
1 1
1 4
1 5
1 6
3 8
4 8
6 9
8 9
8
1 1
1 4
1 5
1 6
3 ...

output:

6
6
6
6
7
7
6
6
7
7
6
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
7
7
7
6
6
7
7
6
7
6
7
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
7
7
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
8
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
8
6
6
7
7
6
6
7
7
6
6
7
7
6
7
7
7
6
6
7
7
6
6
7
7
...

result:

ok 62500 numbers

Test #11:

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

input:

62500
8
1 3
1 4
2 5
3 5
3 5
5 6
5 6
6 7
8
1 3
1 4
2 5
3 5
3 5
5 7
5 7
7 8
8
1 3
1 4
2 6
3 6
3 6
5 7
6 7
6 7
8
1 3
1 4
2 7
3 7
3 7
5 8
6 8
7 8
8
1 3
1 4
2 6
3 6
3 6
5 7
6 7
6 8
8
1 3
1 4
2 7
3 7
3 7
5 8
6 8
7 9
8
1 3
1 4
2 6
3 6
3 6
5 7
6 7
7 7
8
1 3
1 4
2 6
3 6
3 6
5 8
6 8
8 8
8
1 3
1 4
2 6
3 6
3 6
...

output:

5
5
5
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
5
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
6
6
4
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
5
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
6
6
4
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
5
5
6
6
5
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
...

result:

ok 62500 numbers

Test #12:

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

input:

62500
8
1 2
1 5
2 7
4 8
5 8
5 8
7 9
8 10
8
1 2
1 5
2 7
4 9
5 9
5 9
7 10
9 11
8
1 2
1 5
2 7
4 8
5 8
5 8
7 9
9 9
8
1 2
1 5
2 7
4 8
5 8
5 8
7 9
9 10
8
1 2
1 5
2 6
4 7
5 7
5 7
7 7
7 7
8
1 2
1 5
2 6
4 8
5 8
5 8
7 8
8 8
8
1 2
1 5
2 6
4 7
5 7
5 7
7 7
7 8
8
1 2
1 5
2 6
4 8
5 8
5 8
7 8
8 9
8
1 2
1 5
2 6
4 8
...

output:

6
6
6
6
5
6
6
6
5
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
6
7
7
7
7
7
7
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
7
7
6
7
7
7
6
7
7
7
6
7
7
7
7
7
6
7
7
7
7
7
5
5
6
6
5
5
6
6
5
5
6
6
5
6
6
6
5
6
...

result:

ok 62500 numbers

Test #13:

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

input:

62500
8
1 3
2 4
2 4
2 7
3 8
6 9
7 10
7 10
8
1 3
2 4
2 4
2 8
3 9
6 10
7 11
8 11
8
1 3
2 4
2 4
2 7
3 8
6 9
7 10
7 11
8
1 3
2 4
2 4
2 8
3 9
6 10
7 11
8 12
8
1 3
2 4
2 4
2 7
3 8
6 9
7 10
8 10
8
1 3
2 4
2 4
2 7
3 9
6 10
7 11
9 11
8
1 3
2 4
2 4
2 7
3 8
6 9
7 10
8 11
8
1 3
2 4
2 4
2 7
3 9
6 10
7 11
9 12
8
...

output:

6
6
7
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
6
7
7
6
7
4
5
5
5
5
6
6
6
5
5
6
6
5
6
5
6
6
6
6
6
5
5
6
6
5
6
6
6
5
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
6
7
7
6
7
3
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
4
4
5
5
4
4
5
5
...

result:

ok 62500 numbers

Test #14:

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

input:

62500
8
1 2
2 3
2 5
2 5
5 5
5 6
5 7
6 8
8
1 2
2 3
2 5
2 5
5 5
5 7
5 8
7 9
8
1 2
2 3
2 5
2 5
5 5
5 6
5 7
7 7
8
1 2
2 3
2 5
2 5
5 5
5 6
5 7
7 8
8
1 2
2 3
2 6
2 6
5 6
5 7
6 8
6 8
8
1 2
2 3
2 7
2 7
5 7
5 8
6 9
7 9
8
1 2
2 3
2 6
2 6
5 6
5 7
6 8
6 9
8
1 2
2 3
2 7
2 7
5 7
5 8
6 9
7 10
8
1 2
2 3
2 6
2 6
5 6...

output:

7
7
6
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
6
7
7
6
7
5
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
6
7
6
7
7
7
7
7
7
7
7
7
6
7
7
7
6
7
7
7
7
7
4
4
5
5
4
5
5
5
4
5
5
5
5
5
5
5
5
5
6
6
5
5
6
6
5
6
5
5
6
6
5
5
6
6
5
6
4
5
5
5
5
6
6
6
5
5
6
6
5
6
5
6
6
6
6
6
4
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
...

result:

ok 62500 numbers

Test #15:

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

input:

62500
8
1 2
2 3
2 5
3 8
5 9
7 10
8 10
10 11
8
1 2
2 3
2 5
3 8
5 9
7 11
8 11
11 12
8
1 2
2 3
2 5
3 7
5 8
7 9
7 10
7 10
8
1 2
2 3
2 5
3 8
5 9
7 10
7 11
8 11
8
1 2
2 3
2 5
3 7
5 8
7 9
7 10
7 11
8
1 2
2 3
2 5
3 8
5 9
7 10
7 11
8 12
8
1 2
2 3
2 5
3 7
5 8
7 9
7 10
8 10
8
1 2
2 3
2 5
3 7
5 9
7 10
7 11
9 11...

output:

7
7
7
7
8
8
7
7
8
8
7
7
8
8
7
8
7
7
8
8
7
7
8
8
7
7
8
8
7
8
6
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
7
7
8
8
7
7
8
8
7
8
7
7
8
8
7
7
8
8
7
8
6
7
7
7
7
7
8
8
7
8
5
6
6
6
6
7
7
7
6
6
7
7
6
7
6
7
7
7
7
7
6
6
7
7
6
7
7
7
6
7
7
7
7
7
7
7
7
7
8
8
7
7
8
8
7
8
7
7
8
8
7
7
8
8
7
8
6
7
7
7
7
7
8
8
7
8
4
5
5
5
5
6
6
6
...

result:

ok 62500 numbers

Test #16:

score: 0
Accepted
time: 20ms
memory: 7880kb

input:

62500
8
1 4
2 6
3 7
4 8
5 9
6 9
7 10
7 11
8
1 4
2 6
3 8
4 9
5 10
6 10
7 11
8 12
8
1 4
2 6
3 7
4 8
5 9
6 9
7 10
8 10
8
1 4
2 6
3 7
4 9
5 10
6 10
7 11
9 11
8
1 4
2 6
3 7
4 8
5 9
6 9
7 10
8 11
8
1 4
2 6
3 7
4 9
5 10
6 10
7 11
9 12
8
1 4
2 6
3 7
4 8
5 9
6 9
7 10
9 10
8
1 4
2 6
3 7
4 8
5 10
6 10
7 11
10 ...

output:

8
8
8
8
8
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
8
8
7
8
8
8
7
8
8
8
7
8
8
8
8
8
7
8
8
8
8
8
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
7
7
6
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
8
7
7
8
8
7
7
...

result:

ok 62500 numbers

Test #17:

score: 0
Accepted
time: 3ms
memory: 8008kb

input:

10936
8
1 2
2 4
3 6
4 7
4 8
4 8
6 8
7 8
8
1 2
2 4
3 6
4 8
4 9
4 9
6 9
8 9
8
1 2
2 4
3 6
4 7
4 8
4 8
6 8
7 9
8
1 2
2 4
3 6
4 8
4 9
4 9
6 9
8 10
8
1 2
2 4
3 6
4 7
4 8
4 8
6 8
8 8
8
1 2
2 4
3 6
4 7
4 9
4 9
6 9
9 9
8
1 2
2 4
3 6
4 7
4 8
4 8
6 8
8 9
8
1 2
2 4
3 6
4 7
4 9
4 9
6 9
9 10
8
1 2
2 4
3 5
4 6
4 ...

output:

6
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
6
7
7
6
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
7
6
6
7
7
6
6
7
7
6
7
5
6
6
6
6
7
7
7
6
6
7
7
6
7
6
7
7
7
7
7
5
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
7
6
7
7
7
7
7
7
7
...

result:

ok 10936 numbers

Test #18:

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

input:

9653
1
30015435 30015435
2
560111483 560111483
560111483 560111483
3
671161719 671161719
671161719 671161719
671161719 671161719
4
164070441 164070441
164070441 164070441
164070441 164070441
164070441 164070441
5
131260535 131260535
131260535 131260535
131260535 131260535
131260535 131260535
1312605...

output:

1
1
1
1
1
1
2
2
2
2
2
3
3
3
2
2
2
3
3
3
3
2
2
3
3
3
3
3
2
2
2
3
3
3
3
3
4
4
4
3
3
3
4
4
4
4
3
3
4
4
4
4
4
2
2
2
2
3
3
3
3
3
3
2
2
3
3
3
3
3
3
3
3
3
3
4
4
3
3
4
4
4
4
3
3
3
4
4
3
3
4
4
4
4
3
3
4
4
4
3
3
4
4
4
4
4
2
2
2
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
3
3
3
4
4
3
3
4
4
4
4
3
3
4
4
4
4
4
4
4
4
4
3
3
4
...

result:

ok 9653 numbers

Test #19:

score: 0
Accepted
time: 26ms
memory: 11976kb

input:

40000
7
678310982 678310982
678310982 678310982
678310982 678310982
678310982 678310982
678310982 678310982
678310982 678310982
678310982 678310982
7
210257381 485183246
210257381 485183246
210257381 485183246
210257381 485183246
210257381 485183246
210257381 485183246
485183246 485183246
7
26133619...

output:

1
2
2
2
2
3
3
3
2
2
3
3
3
3
2
3
3
3
3
3
2
3
3
3
3
4
4
4
3
3
4
4
4
4
3
4
4
4
4
4
2
2
3
3
3
3
3
3
2
3
3
3
3
3
3
3
3
3
4
4
3
3
4
4
4
4
3
3
4
4
3
3
4
4
4
4
3
4
4
4
3
4
4
4
4
4
2
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
3
3
4
4
3
3
4
4
4
4
3
4
4
4
4
4
4
4
4
4
3
4
4
4
3
4
4
4
4
4
2
3
3
3
3
4
4
4
3
3
4
4
4
4
3
4
4
4
...

result:

ok 40000 numbers

Test #20:

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

input:

35412
7
137686946 139179432
137686946 388616911
139179432 465280990
184972976 606619589
227442399 843832933
388616911 843832933
465280990 843832933
7
173446650 301063237
173446650 473272425
301063237 759102539
378957531 780576289
465003986 953192750
473272425 953192750
759102539 953192750
7
5731930 ...

output:

6
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
5
6
6
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
6
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
6
7
7
7
7
7
4
5
5
5
...

result:

ok 35412 numbers

Test #21:

score: 0
Accepted
time: 42ms
memory: 8008kb

input:

62500
8
202793139 202793139
202793139 202793139
202793139 202793139
202793139 202793139
202793139 202793139
202793139 202793139
202793139 202793139
202793139 202793139
8
967302241 982889607
967302241 982889607
967302241 982889607
967302241 982889607
967302241 982889607
967302241 982889607
967302241 ...

output:

1
2
2
2
2
3
3
3
2
2
3
3
3
3
2
3
3
3
3
3
2
3
3
3
3
4
4
4
3
3
4
4
4
4
3
4
4
4
4
4
2
2
3
3
3
3
3
3
2
3
3
3
3
3
3
3
3
3
4
4
3
3
4
4
4
4
3
3
4
4
3
3
4
4
4
4
3
4
4
4
3
4
4
4
4
4
2
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
3
3
4
4
3
3
4
4
4
4
3
4
4
4
4
4
4
4
4
4
3
4
4
4
3
4
4
4
4
4
2
3
3
3
3
4
4
4
3
3
4
4
4
4
3
4
4
4
...

result:

ok 62500 numbers

Test #22:

score: 0
Accepted
time: 43ms
memory: 11976kb

input:

62500
8
22334282 347814460
22334282 347814460
109879832 501554044
347814460 667483008
347814460 667483008
347814460 667483008
501554044 931484764
667483008 990701760
8
320421451 385561436
320421451 385561436
365223027 633520867
385561436 822725378
385561436 822725378
385561436 822725378
633520867 96...

output:

5
5
5
5
4
5
5
5
4
5
5
5
4
5
5
5
5
5
4
5
5
5
5
5
4
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
5
5
6
6
6
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
4
4
5
5
4
4
5
5
4
4
5
5
5
5
5
5
4
5
...

result:

ok 62500 numbers

Test #23:

score: 0
Accepted
time: 44ms
memory: 8012kb

input:

62500
8
136296443 672006606
521890415 672006606
672006606 763936940
672006606 763936940
763936940 829600368
763936940 829600368
829600368 829600368
829600368 829600368
8
179993721 247626669
239875367 247626669
247626669 794889746
247626669 794889746
794889746 856719032
794889746 856719032
817917681 ...

output:

5
6
6
6
5
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
7
7
7
7
7
7
6
7
7
7
6
7
7
7
6
7
7
7
7
7
6
7
7
7
7
7
5
5
6
6
5
5
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
6
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
7
7
6
6
...

result:

ok 62500 numbers

Test #24:

score: 0
Accepted
time: 43ms
memory: 11940kb

input:

62500
8
82637807 177317970
82637807 759506568
177317970 759506568
177317970 759506568
308720952 871662647
362073769 938545155
759506568 938545155
759506568 983796393
8
17244055 157185811
17244055 722766053
157185811 722766053
157185811 722766053
341336744 951761695
538606813 975708436
603573774 9757...

output:

6
6
6
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
5
5
6
6
6
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
6
6
4
5
5
5
5
6
6
6
5
5
6
6
6
6
5
6
6
6
6
6
4
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
6
6
...

result:

ok 62500 numbers

Test #25:

score: 0
Accepted
time: 45ms
memory: 9936kb

input:

62500
8
50599731 50599731
50599731 464418159
50599731 472105082
50599731 848680988
271125068 864135025
464418159 864135025
848680988 864135025
864135025 972531431
8
169956245 169956245
169956245 288174701
169956245 335938621
169956245 489026065
273189396 561562626
288174701 561562626
489026065 56156...

output:

6
6
6
6
7
7
6
6
7
7
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
6
7
7
7
6
7
7
7
7
7
6
7
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
7
7
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
8
8
6
6
7
7
6
6
7
7
6
6
7
7
7
7
7
7
6
6
7
7
6
6
7
7
...

result:

ok 62500 numbers

Test #26:

score: 0
Accepted
time: 48ms
memory: 8012kb

input:

62500
8
47532282 422409085
47532282 581987562
181396855 592496471
422409085 592496471
422409085 592496471
592496471 669593591
592496471 669593591
669593591 686472613
8
34501394 126838972
34501394 365123131
71437905 406918708
126838972 406918708
126838972 406918708
406918708 464855989
406918708 46485...

output:

5
5
5
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
6
6
4
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
6
6
4
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
5
5
6
6
6
6
5
6
6
6
6
6
6
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
5
6
6
6
...

result:

ok 62500 numbers

Test #27:

score: 0
Accepted
time: 46ms
memory: 10060kb

input:

62500
8
22588317 537285214
22588317 653092928
537285214 897413825
631725704 935542245
653092928 935542245
653092928 935542245
897413825 966901716
935542245 988554116
8
18864112 151873442
18864112 590950372
151873442 631654505
473454245 840448648
590950372 840448648
590950372 840448648
631654505 8680...

output:

6
6
6
6
5
6
6
6
5
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
7
7
7
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
7
7
6
7
7
7
6
7
7
7
6
7
7
7
7
7
6
7
7
7
7
7
5
5
6
6
5
5
6
6
5
5
6
6
6
6
6
6
5
6
...

result:

ok 62500 numbers

Test #28:

score: 0
Accepted
time: 45ms
memory: 8012kb

input:

62500
8
223192637 259851125
241512338 287101470
241512338 287101470
241512338 467061872
259851125 531197478
460558236 621260983
467061872 735205450
467061872 735205450
8
105108560 164991251
134055989 183467777
134055989 183467777
134055989 694034396
164991251 774298126
508031256 774570362
611044086 ...

output:

6
6
7
7
6
6
7
7
6
6
7
7
7
7
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
6
7
7
7
7
7
5
6
6
6
6
7
7
7
6
6
7
7
7
7
6
7
7
7
7
7
5
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
7
7
7
7
7
7
6
7
7
7
6
7
7
7
7
7
3
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
4
4
5
5
4
4
5
5
...

result:

ok 62500 numbers

Test #29:

score: 0
Accepted
time: 44ms
memory: 11980kb

input:

62500
8
80173769 178482926
178482926 253931855
178482926 623292690
178482926 623292690
623292690 623292690
623292690 672340741
623292690 678410880
672340741 824379870
8
214800774 222088815
222088815 303835327
222088815 335724546
222088815 335724546
335724546 335724546
335724546 533613298
335724546 8...

output:

7
7
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
6
7
7
7
7
7
5
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
7
7
7
7
7
7
6
7
7
7
6
7
7
7
7
7
4
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
5
5
6
6
5
5
6
6
6
6
5
6
6
6
6
6
6
6
6
6
5
6
6
6
5
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
5
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
...

result:

ok 62500 numbers

Test #30:

score: 0
Accepted
time: 47ms
memory: 11980kb

input:

62500
8
91865542 149316580
149316580 177354792
149316580 289402953
177354792 636393484
289402953 782449527
519783521 789430881
636393484 789430881
789430881 911879832
8
33529002 47716180
47716180 71316119
47716180 173269912
71316119 194001818
173269912 233791290
190193892 585717609
194001818 5857176...

output:

7
7
7
7
8
8
7
7
8
8
7
7
8
8
8
8
7
7
8
8
7
7
8
8
7
7
8
8
8
8
6
7
7
7
7
7
7
7
6
7
7
7
7
7
7
7
7
7
8
8
7
7
8
8
8
8
7
7
8
8
7
7
8
8
8
8
7
8
8
8
7
8
8
8
8
8
6
7
7
7
7
8
8
8
7
7
8
8
8
8
7
8
8
8
8
8
6
7
7
7
7
7
7
7
7
8
8
8
8
8
8
8
7
7
8
8
7
7
8
8
8
8
7
8
8
8
8
8
8
8
8
8
7
8
8
8
7
8
8
8
8
8
5
6
6
6
6
7
7
7
...

result:

ok 62500 numbers

Test #31:

score: 0
Accepted
time: 47ms
memory: 8008kb

input:

62500
8
59765682 147428647
75824438 261932244
82266823 386837628
147428647 668476160
225920440 822216637
261932244 822216637
386837628 873112707
386837628 974222998
8
61527723 423261185
84169283 542268712
185568324 693321260
423261185 822510488
475487954 840803824
542268712 840803824
668894502 88503...

output:

8
8
8
8
8
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
8
8
7
8
8
8
8
8
8
8
8
8
7
8
8
8
7
8
8
8
7
8
8
8
8
8
7
8
8
8
8
8
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
7
7
6
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
7
7
8
8
8
8
7
7
8
8
7
7
...

result:

ok 62500 numbers

Test #32:

score: 0
Accepted
time: 7ms
memory: 12108kb

input:

10936
8
189992530 488954270
488954270 584812126
491772106 813538910
584812126 821722949
584812126 960612669
584812126 960612669
813538910 960612669
821722949 960612669
8
183550650 264093697
264093697 394026441
266291931 686830157
394026441 843555749
394026441 986497257
394026441 986497257
686830157 ...

output:

6
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
6
6
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
5
6
6
6
6
6
6
6
5
6
6
6
6
6
6
6
6
6
7
7
6
6
7
7
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
6
7
7
7
6
7
7
7
7
7
6
7
7
7
7
7
5
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
6
6
7
7
6
6
7
7
6
6
7
7
6
6
7
7
7
7
6
7
7
7
7
7
7
7
...

result:

ok 10936 numbers

Test #33:

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

input:

100000
10
1 1
1 2
1 2
2 3
2 3
3 4
4 4
4 4
4 5
5 5
3
1 2
2 3
2 5
2
2 5
3 5
6
2 2
2 3
3 5
4 5
5 5
5 5
2
2 5
5 5
13
1 1
1 1
1 2
1 2
2 3
3 3
3 3
3 4
3 4
4 4
4 5
5 5
5 5
8
1 3
2 3
2 4
3 4
4 5
4 5
5 5
5 5
3
1 3
1 4
2 5
4
1 2
2 4
3 4
4 5
4
1 3
2 4
3 5
5 5
1
4 4
1
2 5
1
2 4
2
2 4
4 5
5
1 2
2 3
2 4
2 5
2 5
3...

output:

5
3
2
4
2
5
5
3
4
4
1
1
1
2
4
3
1
2
4
4
5
2
4
2
3
5
5
1
2
1
5
3
4
2
5
2
3
4
3
4
5
1
2
1
4
5
2
2
5
5
3
1
1
4
5
1
5
5
3
4
5
1
3
5
4
1
1
1
5
4
1
1
5
3
2
2
4
5
2
4
5
4
2
4
5
1
4
2
3
4
5
4
1
3
4
1
4
5
1
2
2
1
1
5
2
2
1
3
4
1
5
3
1
5
4
4
4
3
1
5
5
1
1
5
1
5
3
2
3
5
5
1
5
4
2
5
4
5
5
5
2
1
5
4
3
3
4
3
4
5
...

result:

ok 100000 numbers

Test #34:

score: 0
Accepted
time: 77ms
memory: 12584kb

input:

10
2991
20 30
23 43
32 52
37 70
48 85
54 91
74 116
98 150
102 243
126 247
135 247
140 277
166 280
173 303
177 314
184 372
246 386
268 396
274 402
302 417
307 417
309 420
377 423
392 429
426 445
427 479
443 484
483 504
485 517
513 529
522 544
543 575
547 598
564 608
565 626
573 628
584 636
620 650
64...

output:

2930
14474
41911
17073
24522
41275
32256
23631
32803
45637

result:

ok 10 numbers

Test #35:

score: -100
Wrong Answer
time: 128ms
memory: 12524kb

input:

10
102520
1851 15493
5340 18694
6527 27722
22838 37137
31626 51201
38030 65798
61184 78073
68636 80483
80262 84436
82607 121271
90688 143122
99500 154714
102256 161895
109403 164250
112421 166978
116270 189423
120877 191889
137567 229352
154131 231338
174191 243499
178884 243841
188710 249563
195073...

output:

100013
20633
63027
70704
100011
37772
7927
22371
17803
51011

result:

wrong answer 1st numbers differ - expected: '102519', found: '100013'