QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#839837#3310. Steel Slicing 2Kevin5307AC ✓309ms79396kbC++232.7kb2025-01-02 10:29:322025-01-02 10:29:40

Judging History

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

  • [2025-01-02 10:29:40]
  • 评测
  • 测评结果:AC
  • 用时:309ms
  • 内存:79396kb
  • [2025-01-02 10:29:32]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
#define ls (x<<1)
#define rs (ls|1)
int h[300300],l[300300],n;
vector<int> vec[300300];
int sth[20][300300],stl[20][300300];
int geth(int l,int r)
{
	int x=__lg(r-l+1);
	return min(sth[x][l],sth[x][r-(1<<x)+1]);
}
int getl(int l,int r)
{
	int x=__lg(r-l+1);
	return min(stl[x][l],stl[x][r-(1<<x)+1]);
}
map<int,int> Lst;
int mn[300300<<2],segt[300300<<2];
void modify(int x,int l,int r,int p,int v)
{
	if(l==r)
	{
		mn[x]=v;
		return ;
	}
	int mid=(l+r)/2;
	if(p<=mid) modify(ls,l,mid,p,v);
	else modify(rs,mid+1,r,p,v);
	mn[x]=segt[x]+min(mn[ls],mn[rs]);
}
int query(int x,int l,int r,int ql,int qr)
{
	if(l==ql&&r==qr) return mn[x];
	int mid=(l+r)/2;
	if(qr<=mid) return segt[x]+query(ls,l,mid,ql,qr);
	if(ql>mid) return segt[x]+query(rs,mid+1,r,ql,qr);
	return segt[x]+min(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
}
void update(int x,int l,int r,int ql,int qr,int v)
{
	if(ql<=l&&r<=qr)
	{
		segt[x]+=v;
		mn[x]+=v;
		return ;
	}
	int mid=(l+r)/2;
	if(ql<=mid) update(ls,l,mid,ql,qr,v);
	if(qr>mid) update(rs,mid+1,r,ql,qr,v);
	mn[x]=segt[x]+min(mn[ls],mn[rs]);
}
int dp[300300];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>h[i]>>l[i];
	for(int i=1;i<=n;i++)
	{
		sth[0][i]=h[i];
		stl[0][i]=l[i];
	}
	for(int i=1;i<20;i++)
		for(int j=1;j<=n;j++)
			if(j+(1<<i-1)<=n)
			{
				sth[i][j]=min(sth[i-1][j],sth[i-1][j+(1<<i-1)]);
				stl[i][j]=min(stl[i-1][j],stl[i-1][j+(1<<i-1)]);
			}
			else
			{
				sth[i][j]=sth[i-1][j];
				stl[i][j]=stl[i-1][j];
			}
	for(int i=1;i<=n;i++)
	{
		if(Lst[h[i]])
			if(geth(Lst[h[i]],i)==h[i])
				vec[i].pb(Lst[h[i]]);
		Lst[h[i]]=i;
	}
	Lst.clear();
	for(int i=1;i<=n;i++)
	{
		if(Lst[l[i]])
			if(getl(Lst[l[i]],i)==l[i])
				vec[i].pb(Lst[l[i]]);
		Lst[l[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1]+1;
		for(auto x:vec[i])
			update(1,0,n,0,x-1,-1);
		dp[i]=min(dp[i],1+query(1,0,n,0,i-1));
		update(1,0,n,0,i-1,2);
		modify(1,0,n,i,dp[i]);
	}
	cout<<dp[n]-1<<'\n';
	return 0;
}

詳細信息

Test #1:

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

input:

8
1 4
4 2
3 2
5 1
6 4
4 2
2 3
5 1

output:

7

result:

ok single line: '7'

Test #2:

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

input:

5
23 15
23 17
3 22
15 3
5 1

output:

4

result:

ok single line: '4'

Test #3:

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

input:

8
1 2
2 2
2 1
1 1
1 2
2 2
2 2
1 2

output:

4

result:

ok single line: '4'

Test #4:

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

input:

2
1 1000000
1000000 1

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1
1 1

output:

0

result:

ok single line: '0'

Test #6:

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

input:

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

output:

0

result:

ok single line: '0'

Test #7:

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

input:

1000
2 1
2 1
1 2
1 2
1 2
1 2
2 2
1 1
1 2
1 2
1 1
1 2
2 1
1 1
1 2
2 2
1 1
2 2
1 2
1 2
2 1
2 1
1 2
1 1
1 2
2 2
2 1
2 2
1 2
2 1
1 2
1 2
2 2
1 2
1 2
2 2
2 1
2 1
2 1
1 2
2 1
2 2
1 1
1 2
2 2
2 1
1 1
1 1
2 1
2 2
2 2
1 1
1 1
1 1
1 1
2 1
2 2
1 2
2 1
2 2
1 1
2 2
2 1
2 1
1 1
2 1
2 1
2 1
1 2
1 1
2 1
2 1
2 1
2 2...

output:

505

result:

ok single line: '505'

Test #8:

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

input:

1000
2 2
3 3
3 1
2 1
1 2
1 1
1 3
2 2
1 2
2 1
3 1
1 3
1 1
3 2
2 3
2 1
2 1
1 2
2 1
3 1
3 1
2 1
1 1
2 2
1 2
2 3
3 1
3 3
2 2
3 1
2 1
3 3
3 3
3 2
2 1
1 1
3 1
3 3
2 1
3 1
1 3
2 3
2 1
2 3
1 3
1 3
1 1
1 2
2 2
3 2
2 1
2 2
2 3
2 2
3 1
2 2
1 1
1 3
1 1
3 3
1 3
3 1
2 2
1 3
2 1
1 1
2 3
3 1
2 1
2 1
3 1
2 3
3 2
1 3...

output:

755

result:

ok single line: '755'

Test #9:

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

input:

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

output:

898

result:

ok single line: '898'

Test #10:

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

input:

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

output:

937

result:

ok single line: '937'

Test #11:

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

input:

1000
6 3
2 6
4 1
1 3
4 2
4 5
5 3
6 5
6 6
2 6
6 3
4 1
5 5
4 3
4 6
2 6
5 5
1 3
3 1
6 3
6 2
6 5
2 2
1 3
2 6
5 1
6 6
1 1
5 3
5 3
4 3
6 2
3 5
2 2
5 2
2 1
3 4
3 3
6 3
4 5
3 4
1 6
2 1
4 3
4 4
4 5
5 6
4 6
5 2
1 6
6 4
3 1
3 2
1 5
6 4
5 5
3 4
4 3
4 1
5 1
1 3
5 1
5 3
5 2
6 4
5 4
5 6
1 5
4 3
2 2
1 1
6 1
5 2
3 6...

output:

962

result:

ok single line: '962'

Test #12:

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

input:

1000
1 2
7 2
7 2
7 4
2 7
7 6
7 6
4 6
2 7
6 4
5 6
4 5
6 5
2 2
7 7
4 3
5 6
2 6
7 3
1 1
1 1
6 2
1 6
6 5
6 6
4 4
1 4
3 1
1 5
3 3
5 4
6 3
2 4
7 7
7 1
5 4
2 4
1 2
5 7
5 6
4 7
6 5
5 5
5 7
6 7
7 6
2 2
5 1
2 6
6 7
7 2
6 2
4 7
7 5
1 5
7 5
5 4
5 3
6 7
7 6
3 5
6 3
5 5
7 6
5 4
2 4
1 6
4 3
4 5
1 2
1 3
6 1
5 1
1 6...

output:

967

result:

ok single line: '967'

Test #13:

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

input:

1000
6 5
5 7
8 8
5 4
7 5
7 6
1 7
2 3
6 7
7 4
4 8
6 8
2 1
2 8
5 6
1 1
5 7
5 5
1 8
5 2
7 8
5 1
5 2
1 8
3 6
6 1
6 1
2 1
7 1
7 1
2 2
4 1
8 3
4 8
5 2
4 5
2 4
1 1
4 6
8 3
3 7
5 2
4 3
5 7
8 1
3 8
3 6
6 6
5 1
1 8
4 4
3 5
8 1
5 7
6 3
6 2
6 1
2 1
5 6
7 2
4 3
6 5
7 4
8 8
6 7
7 6
7 8
8 3
2 8
8 2
4 1
4 7
5 4
7 6...

output:

978

result:

ok single line: '978'

Test #14:

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

input:

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

output:

984

result:

ok single line: '984'

Test #15:

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

input:

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

output:

983

result:

ok single line: '983'

Test #16:

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

input:

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

output:

997

result:

ok single line: '997'

Test #17:

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

input:

1000
45 43
56 96
92 7
59 80
93 9
28 53
71 34
5 89
51 12
29 8
28 32
41 74
96 23
59 4
72 6
98 6
4 26
48 79
65 89
53 35
66 35
63 24
100 53
97 22
25 1
82 12
60 44
88 29
95 67
63 7
84 59
58 11
61 78
10 99
21 11
42 38
60 89
24 68
26 13
6 76
85 11
94 72
3 21
42 20
13 64
61 87
98 57
13 21
33 25
78 31
22 6
5...

output:

999

result:

ok single line: '999'

Test #18:

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

input:

1000
641143 722285
386048 792971
998109 741932
230573 320081
676108 661055
127802 140162
43386 591732
741372 392575
650045 53599
977198 595500
554451 809111
89262 957747
559644 661815
306494 841922
12762 763934
347268 388552
873656 405488
311754 673276
818176 189714
364734 788694
359972 410289
89867...

output:

999

result:

ok single line: '999'

Test #19:

score: 0
Accepted
time: 180ms
memory: 75936kb

input:

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

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 148ms
memory: 75644kb

input:

250000
1 1
1 1
2 1
2 2
2 1
1 2
2 2
1 2
2 1
1 1
2 1
1 1
2 1
2 1
2 2
1 2
1 1
1 1
2 1
1 1
2 2
1 1
2 2
2 2
2 2
2 2
1 2
1 2
1 2
2 1
1 1
1 1
2 1
1 2
2 2
2 1
2 2
2 1
2 1
1 1
2 2
1 1
1 1
1 1
1 2
2 1
2 2
2 2
2 1
2 1
1 2
2 1
2 2
1 2
1 1
2 1
2 2
2 1
1 1
1 2
2 1
1 2
2 2
2 1
1 2
2 2
1 2
2 1
2 1
2 2
2 2
1 1
1 2
1...

output:

124943

result:

ok single line: '124943'

Test #21:

score: 0
Accepted
time: 145ms
memory: 74236kb

input:

250000
2 3
2 3
1 1
2 3
2 1
1 3
2 1
3 2
1 2
2 3
3 3
2 2
3 1
1 2
3 3
3 3
1 1
2 1
1 2
2 1
3 1
3 1
3 3
1 2
1 2
2 1
1 1
2 3
2 1
3 2
3 1
1 2
2 3
3 2
1 1
1 3
3 1
2 2
2 2
1 3
1 3
2 3
1 3
3 2
1 2
2 3
3 2
1 2
1 1
1 3
3 1
2 2
3 3
1 2
2 1
2 3
1 1
1 2
3 2
1 3
2 1
3 3
3 2
3 1
3 1
3 2
3 2
2 1
3 3
1 3
2 3
2 2
3 3
2...

output:

192561

result:

ok single line: '192561'

Test #22:

score: 0
Accepted
time: 144ms
memory: 73760kb

input:

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

output:

224139

result:

ok single line: '224139'

Test #23:

score: 0
Accepted
time: 134ms
memory: 73036kb

input:

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

output:

236156

result:

ok single line: '236156'

Test #24:

score: 0
Accepted
time: 129ms
memory: 72744kb

input:

250000
6 1
1 4
1 1
6 3
3 4
6 2
3 3
6 6
4 3
2 5
1 1
4 4
5 1
5 3
5 6
1 2
2 1
4 2
2 4
6 5
6 5
3 4
1 5
6 4
1 2
2 3
6 3
5 4
5 5
5 5
2 3
2 2
3 4
6 6
4 2
6 6
6 3
5 6
4 1
4 5
4 1
2 4
5 1
1 3
5 1
2 6
2 5
1 4
3 4
3 3
3 1
2 5
6 4
5 3
5 1
1 1
5 2
2 5
1 3
4 1
4 1
2 5
5 2
4 4
6 1
5 3
4 5
2 6
5 6
1 1
4 6
4 5
5 1
1...

output:

241063

result:

ok single line: '241063'

Test #25:

score: 0
Accepted
time: 122ms
memory: 72828kb

input:

250000
6 4
7 1
2 2
4 1
2 7
1 4
7 5
7 5
1 5
1 3
1 4
6 6
3 4
3 1
2 4
1 5
1 5
5 4
3 6
4 2
5 5
4 3
3 2
1 6
4 6
2 4
1 7
4 7
1 2
6 5
7 6
5 5
6 7
7 4
5 7
7 4
7 5
6 4
3 1
2 7
5 3
1 1
7 4
5 2
6 2
7 3
5 5
3 2
6 6
2 4
2 3
3 3
1 5
1 3
4 3
1 5
4 6
5 6
1 6
3 7
6 5
1 4
7 2
1 7
3 5
5 2
1 4
4 6
4 7
4 5
3 5
6 4
1 5
4...

output:

243757

result:

ok single line: '243757'

Test #26:

score: 0
Accepted
time: 133ms
memory: 71776kb

input:

250000
5 1
5 1
7 6
2 6
8 5
1 7
3 8
8 1
7 4
6 1
6 2
8 5
8 1
7 4
6 2
8 1
7 3
2 4
6 5
3 8
1 6
4 6
4 8
8 1
4 8
1 1
5 8
3 8
5 5
7 7
6 1
2 2
7 2
3 8
4 2
8 4
2 5
2 7
4 6
4 3
1 2
8 1
3 3
2 4
1 6
3 4
6 5
7 5
8 6
7 5
1 3
8 1
2 8
3 8
3 8
3 6
4 1
2 3
8 3
4 2
4 4
1 2
5 7
7 8
7 8
7 3
6 2
4 7
1 1
7 3
2 8
5 3
7 5
7...

output:

245457

result:

ok single line: '245457'

Test #27:

score: 0
Accepted
time: 132ms
memory: 72888kb

input:

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

output:

246382

result:

ok single line: '246382'

Test #28:

score: 0
Accepted
time: 134ms
memory: 71680kb

input:

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

output:

247139

result:

ok single line: '247139'

Test #29:

score: 0
Accepted
time: 129ms
memory: 70680kb

input:

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

output:

249366

result:

ok single line: '249366'

Test #30:

score: 0
Accepted
time: 118ms
memory: 69496kb

input:

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

output:

249723

result:

ok single line: '249723'

Test #31:

score: 0
Accepted
time: 127ms
memory: 69696kb

input:

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

output:

249831

result:

ok single line: '249831'

Test #32:

score: 0
Accepted
time: 128ms
memory: 69532kb

input:

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

output:

249889

result:

ok single line: '249889'

Test #33:

score: 0
Accepted
time: 123ms
memory: 68116kb

input:

250000
62 50
56 57
27 47
68 15
41 66
7 24
44 31
11 42
6 59
1 33
53 33
48 70
49 17
59 16
8 60
37 63
9 30
6 74
70 12
2 53
26 14
26 37
20 42
66 73
54 4
59 29
18 25
47 59
1 3
75 65
27 16
4 3
33 66
10 30
43 44
43 32
11 29
69 31
14 14
42 68
3 20
50 10
2 20
73 38
60 11
22 16
64 69
21 12
29 72
49 22
61 63
6...

output:

249962

result:

ok single line: '249962'

Test #34:

score: 0
Accepted
time: 124ms
memory: 69820kb

input:

250000
51 18
14 39
83 50
31 100
63 89
33 3
93 28
10 51
88 77
96 95
9 31
9 47
28 81
19 65
96 91
1 69
35 68
33 9
92 86
60 29
31 5
93 16
21 12
26 93
1 94
89 23
32 67
85 34
41 65
63 4
98 39
77 5
9 25
50 43
20 54
15 66
78 85
84 73
39 81
13 63
12 25
81 55
32 80
67 49
45 9
68 47
65 4
38 21
81 28
57 77
82 9...

output:

249972

result:

ok single line: '249972'

Test #35:

score: 0
Accepted
time: 293ms
memory: 70572kb

input:

250000
154618 123667
38065 78010
171668 237213
172162 238536
155990 209891
243536 119156
97697 113781
40342 37414
202504 153572
245922 31931
32851 179769
127940 171908
196076 168653
36259 69557
197060 179327
69191 234550
131023 87857
2736 42437
110484 98859
144478 40179
68478 63079
13670 31570
22214...

output:

249999

result:

ok single line: '249999'

Test #36:

score: 0
Accepted
time: 309ms
memory: 73236kb

input:

250000
886198 486228
152922 220322
199182 254057
61343 409762
545109 491305
596823 485052
240782 884098
276105 281743
598112 246694
877275 568703
100116 690185
764698 857905
229208 938276
658614 616403
844478 164405
780098 832594
91453 879229
809272 867873
675183 883904
909108 976761
291794 634377
4...

output:

249999

result:

ok single line: '249999'

Test #37:

score: 0
Accepted
time: 183ms
memory: 75052kb

input:

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

output:

198

result:

ok single line: '198'

Test #38:

score: 0
Accepted
time: 187ms
memory: 75116kb

input:

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

output:

1998

result:

ok single line: '1998'

Test #39:

score: 0
Accepted
time: 191ms
memory: 76152kb

input:

250000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 1
2 1
2 1
2 1
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
3 3
3 3
3 3
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 5
3 5
4 5
4 5
4 5
4 5
4 5
4 5
4 6
4 6
4 6
4 6
4 6
4 6
4 6
5 6
5 6
5 6
5 6
5 6
5 6
5 6
5 7
5 7
5 7
5...

output:

19998

result:

ok single line: '19998'

Test #40:

score: 0
Accepted
time: 220ms
memory: 78204kb

input:

250000
1 1
1 2
3 2
3 2
3 2
4 3
6 5
7 5
7 5
7 5
10 5
10 6
11 7
11 8
12 8
13 9
14 9
15 9
16 11
18 11
22 12
22 12
23 12
25 12
26 13
27 17
27 17
28 17
28 17
28 17
30 18
30 19
31 19
31 19
33 20
33 20
33 21
35 22
35 23
36 23
37 26
37 27
37 28
38 28
38 29
39 32
41 32
41 34
41 35
42 36
43 36
44 37
44 38
45 ...

output:

183603

result:

ok single line: '183603'

Test #41:

score: 0
Accepted
time: 201ms
memory: 79396kb

input:

250000
2 11
17 16
28 24
36 42
40 42
53 45
58 47
61 55
73 55
82 64
84 66
87 68
101 70
105 76
115 81
118 89
121 98
136 100
144 100
144 103
146 118
178 118
179 135
182 136
191 144
196 168
201 190
206 190
222 191
251 218
260 225
270 231
289 238
290 247
293 249
313 257
323 267
336 274
336 292
346 293
346...

output:

249073

result:

ok single line: '249073'

Test #42:

score: 0
Accepted
time: 218ms
memory: 79276kb

input:

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

output:

249999

result:

ok single line: '249999'