QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725427#1962. Security Systemucup-team3161#AC ✓96ms223472kbC++175.6kb2024-11-08 17:41:302024-11-08 17:41:30

Judging History

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

  • [2024-11-08 17:41:30]
  • 评测
  • 测评结果:AC
  • 用时:96ms
  • 内存:223472kb
  • [2024-11-08 17:41:30]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;

#define maxn 2000005
#define inf 0x3f3f3f3f
#define pb push_back
typedef vector<int>vi;

int n,x[maxn],y[maxn];

int tmpx[maxn],tmpy[maxn],nx,ny;
void workx(int ds[]) {sort(ds+1,ds+ds[0]+1);ds[0]=unique(ds+1,ds+ds[0]+1)-ds-1;}

int l[maxn],r[maxn];

int f[maxn],g[maxn];

int mxl[20][maxn],mnr[20][maxn];
int qmaxl(int l,int r){
    int k=__lg(r-l+1);
    return max(mxl[k][l],mxl[k][r-(1<<k)+1]);
}
int qminr(int l,int r){
    int k=__lg(r-l+1);
    return min(mnr[k][l],mnr[k][r-(1<<k)+1]);
}

int nxt[maxn];

struct segt{
    int tag[maxn<<2],mn[maxn<<2];
    void init(){
        memset(mn,63,sizeof mn);
        memset(tag,63,sizeof tag);
    }
    int ask(int p,int l,int r,int ql,int qr){
        if(ql>qr)return inf;
        if(l>=ql && r<=qr) return mn[p];
        //cout<<"ask "<<p<<" "<<l<<" "<<r<<"\n";
        int mid=l+r>>1,res=tag[p];
        if(ql<=mid)res=min(res,ask(p<<1,l,mid,ql,qr));
        if(qr>mid)res=min(res,ask(p<<1|1,mid+1,r,ql,qr));
        return res;
    }
    void mdf(int p,int l,int r,int ql,int qr,int t){
        if(ql>qr)return;
        if(l>=ql&&r<=qr){
            tag[p]=min(tag[p],t);
            mn[p]=min(mn[p],t);
            return;
        }
        int mid=l+r>>1;
        if(ql<=mid)mdf(p<<1,l,mid,ql,qr,t);
        if(qr>mid)mdf(p<<1|1,mid+1,r,ql,qr,t);
        mn[p]=min(min(tag[p],mn[p<<1]),mn[p<<1|1]);
    }
    int ask(int ql,int qr){
        return ask(1,1,nx,ql,qr);
    }
    void mdf(int ql,int qr,int v){
        mdf(1,1,nx,ql,qr,v);
    }
}F,G;


int pre1[maxn],pre2[maxn],pre3[maxn],pre4[maxn];
int l2[maxn],r2[maxn];

int main()
{
    cin>>n;
    For(i,1,n)cin>>x[i]>>y[i];
    
    tmpx[0]=0; For(i,1,n)tmpx[++tmpx[0]]=x[i];
    workx(tmpx); nx=tmpx[0];
    For(i,1,n)x[i]=lower_bound(tmpx+1,tmpx+tmpx[0]+1,x[i])-tmpx;

    tmpy[0]=0; For(i,1,n)tmpy[++tmpy[0]]=y[i];
    workx(tmpy); ny=tmpy[0];
    For(i,1,n)y[i]=lower_bound(tmpy+1,tmpy+tmpy[0]+1,y[i])-tmpy;

    For(i,1,nx) l[i]=-1,r[i]=inf;
    For(i,1,n) {
        int j=i+1; if(j>n) j=1;
        if(y[i]!=y[j]){
            
        }else{
            if(x[i]<x[j]){
                For(k,x[i],x[j]-1) l[k]=max(l[k],y[i]);
            }else{
                For(k,x[j],x[i]-1) r[k]=min(r[k],y[i]);
            }
        }
    }
    For(i,1,nx) --r[i];
    --nx;

  /*  For(i,1,nx){
       cout<<"l,r "<<l[i]<<" "<<r[i]<<"\n";
    }
 cout<<"-----\n";*/

    /*int nx2=0;
    For(i,1,nx) {
        l2[++nx2]=l[i],r2[nx2]=r[i];
        if(i==nx) continue;
        l2[++nx2]=min(l[i],l[i+1]);
        r2[nx2]=max(r[i],r[i+1]);
    }
    nx=nx2;
    For(i,1,nx) l[i]=l2[i],r[i]=r2[i];
    */

  /* For(i,1,nx){
       cout<<"l,r "<<l[i]<<" "<<r[i]<<"\n";
    }
 cout<<"-----\n";*/

    For(i,1,nx){
        mxl[0][i]=l[i];
        mnr[0][i]=r[i];
    }
    For(j,1,19){
        For(i,1,nx-(1<<j)+1){
            mxl[j][i]=max(mxl[j-1][i],mxl[j-1][i+(1<<(j-1))]);
            mnr[j][i]=min(mnr[j-1][i],mnr[j-1][i+(1<<(j-1))]);
        }
    }

    int res=inf;
    f[0]=g[0]=0;
    For(i,1,nx) f[i]=g[i]=inf;

    int pre=0;

    nxt[nx]=nx+1;
    Rep(i,nx-1,0){
        if(l[i]>l[i+1] || r[i]<r[i+1]) nxt[i]=i;
        else nxt[i]=nxt[i+1];
    }

    For(i,2,nx){
        pre1[i]=pre1[i-1],pre2[i]=pre2[i-1];
        pre3[i]=pre3[i-1],pre4[i]=pre4[i-1];
        if(r[i-1]<r[i]) pre1[i]=i;
        if(r[i-1]>r[i]) pre2[i]=i;
        if(l[i-1]<l[i]) pre3[i]=i;
        if(l[i-1]>l[i]) pre4[i]=i;
    }

    F.init(),G.init();

    int nl=l[1],nr=r[1];
    For(i,1,nx){
        nl=max(nl,l[i]);
        nr=min(nr,r[i]);
        if(nl<=nr) G.mdf(i,i,1);
    }

    For(i,1,nx){
     //   cout<<"i: "<<i<<" "<<l[i]<<" "<<r[i]<<"\n";
        int ps=0,ql=1,qr=i-1;
        while(ql<=qr){
            int mid=ql+qr>>1;
            if(qmaxl(mid,i) <= qminr(mid,i)+1) qr=mid-1;
            else ps=mid,ql=mid+1;//cout<<"Qmaxl,minr "<<mid<<" "<<i<<" "<<qmaxl(mid,i)<<" "<<qminr(mid,i)<<"\n";
        }++ps;

        {
            int u=pre1[pre2[i]];
         //   cout<<"R[u] "<<i<<" "<<u<<"\n";
            ps=max(ps,u);
            u=pre4[pre3[i]];
        //    cout<<"L[u] "<<i<<" "<<u<<"\n";
            ps=max(ps,u);
         //   cout<<"ps "<<ps<<"\n";
        }

      /*  Rep(j,i-1,ps){
            f[i]=min(f[i],f[j]+1);
        }*/

        int val=F.ask(ps,i-1)+1; 
        F.mdf(i,i,val);

        if(l[i-1]<l[i] || r[i-1]>r[i]) pre=i-1;

        int id=pre;
        if(!id) F.mdf(i,i,1);
        else {
            int val=G.ask(id,i-1)+1;
            F.mdf(i,i,val);
        }

        
        ps=nxt[i];
         val=F.ask(i,i);
        G.mdf(i+1,ps,val);
       // For(j,i+1,ps) g[j]=min(g[j],f[i]);

       /* For(j,i+1,nx){
            if(l[j-1]>l[j] || r[j-1]<r[j]) {
                break;
            }
            g[j]=min(g[j],f[i]);
        }*/
        

        ql=i+1,qr=nx,ps=nx+1;
        while(ql<=qr){
            int mid=ql+qr>>1;
            if(qmaxl(i+1,mid) <= qminr(i+1,mid)) ql=mid+1;
            else qr=mid-1,ps=mid;
        } --ps;

         val=G.ask(i,i)+1;
         G.mdf(i+1,ps,val);
      //  For(j,i+1,ps) g[j]=min(g[j],g[i]+1);

        /*int L=l[i],R=r[i];
        For(j,i+1,nx){
            L=max(L,l[j]),R=min(R,r[j]);
            if(L<=R) g[j]=min(g[j],g[i]+1);
            else break;
        }*/
     //   cout<<"i: "<<i<<" "<<F.ask(i,i)<<" "<<G.ask(i,i)<<"\n";
    }
    cout<<min(F.ask(nx,nx),G.ask(nx,nx));
    return 0;
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 159236kb

input:

16
2 1
11 1
11 7
13 7
13 3
17 3
17 6
15 6
15 9
8 9
8 6
5 6
5 9
1 9
1 4
2 4

output:

2

result:

ok single line: '2'

Test #2:

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

input:

34
29 5
29 11
26 11
26 9
23 9
23 12
20 12
20 11
15 11
15 5
13 5
13 10
11 10
11 13
8 13
8 7
5 7
5 11
1 11
1 2
6 2
6 4
9 4
9 8
12 8
12 1
18 1
18 6
22 6
22 3
25 3
25 7
27 7
27 5

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 4ms
memory: 161456kb

input:

20
1 2
5 2
5 6
7 6
7 1
15 1
15 6
17 6
17 2
19 2
19 8
13 8
13 5
9 5
9 10
6 10
6 8
3 8
3 5
1 5

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 4ms
memory: 163460kb

input:

20
1 2
5 2
5 5
7 5
7 1
15 1
15 5
17 5
17 2
19 2
19 8
13 8
13 5
9 5
9 10
6 10
6 8
3 8
3 5
1 5

output:

3

result:

ok single line: '3'

Test #5:

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

input:

8
1 3
4 3
4 1
7 1
7 6
4 6
4 8
1 8

output:

1

result:

ok single line: '1'

Test #6:

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

input:

12
1 1
5 1
5 4
8 4
8 6
6 6
6 9
4 9
4 7
2 7
2 3
1 3

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 4ms
memory: 159284kb

input:

12
1 1
4 1
4 4
8 4
8 6
6 6
6 9
4 9
4 7
2 7
2 3
1 3

output:

2

result:

ok single line: '2'

Test #8:

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

input:

12
1 4
5 4
5 1
8 1
8 3
7 3
7 7
5 7
5 9
3 9
3 6
1 6

output:

2

result:

ok single line: '2'

Test #9:

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

input:

12
1 4
4 4
4 1
8 1
8 3
7 3
7 7
5 7
5 9
3 9
3 6
1 6

output:

1

result:

ok single line: '1'

Test #10:

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

input:

24
20 1
20 7
18 7
18 4
16 4
16 7
12 7
12 4
9 4
9 7
5 7
5 4
3 4
3 7
1 7
1 1
6 1
6 5
8 5
8 1
13 1
13 5
15 5
15 1

output:

4

result:

ok single line: '4'

Test #11:

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

input:

4
-1 -1
1 -1
1 1
-1 1

output:

1

result:

ok single line: '1'

Test #12:

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

input:

20
0 0
30 0
30 20
40 20
40 0
70 0
70 20
80 20
80 0
90 0
90 30
60 30
60 10
50 10
50 30
20 30
20 10
10 10
10 30
0 30

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 84ms
memory: 223472kb

input:

100000
0 0
30 0
30 20
40 20
40 0
70 0
70 20
80 20
80 0
110 0
110 20
120 20
120 0
150 0
150 20
160 20
160 0
190 0
190 20
200 20
200 0
230 0
230 20
240 20
240 0
270 0
270 20
280 20
280 0
310 0
310 20
320 20
320 0
350 0
350 20
360 20
360 0
390 0
390 20
400 20
400 0
430 0
430 20
440 20
440 0
470 0
470 2...

output:

16667

result:

ok single line: '16667'

Test #14:

score: 0
Accepted
time: 11ms
memory: 166344kb

input:

50
27 4
27 8
25 8
25 12
23 12
23 10
21 10
21 6
19 6
19 16
17 16
17 18
16 18
16 21
14 21
14 19
12 19
12 15
11 15
11 12
9 12
9 19
7 19
7 18
5 18
5 10
2 10
2 8
1 8
1 6
4 6
4 7
7 7
7 4
8 4
8 1
9 1
9 9
10 9
10 11
14 11
14 8
17 8
17 5
19 5
19 3
22 3
22 7
23 7
23 4

output:

4

result:

ok single line: '4'

Test #15:

score: 0
Accepted
time: 4ms
memory: 163460kb

input:

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

output:

2

result:

ok single line: '2'

Test #16:

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

input:

50
31 2
31 5
30 5
30 6
28 6
28 8
26 8
26 10
22 10
22 5
20 5
20 14
18 14
18 8
16 8
16 9
15 9
15 6
13 6
13 16
7 16
7 14
3 14
3 11
1 11
1 7
4 7
4 5
6 5
6 12
8 12
8 8
10 8
10 1
12 1
12 3
13 3
13 1
15 1
15 3
17 3
17 7
19 7
19 2
24 2
24 7
26 7
26 3
29 3
29 2

output:

6

result:

ok single line: '6'

Test #17:

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

input:

14
-30000000 -20000000
30000000 -20000000
30000000 0
20000000 0
20000000 10000000
10000000 10000000
10000000 -10000000
0 -10000000
0 20000000
-10000000 20000000
-10000000 10000000
-20000000 10000000
-20000000 0
-30000000 0

output:

1

result:

ok single line: '1'

Test #18:

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

input:

36
19 2
19 8
17 8
17 6
15 6
15 10
13 10
13 5
11 5
11 8
9 8
9 5
7 5
7 10
5 10
5 6
3 6
3 8
1 8
1 1
3 1
3 5
5 5
5 2
7 2
7 4
9 4
9 2
11 2
11 4
13 4
13 2
15 2
15 5
17 5
17 2

output:

3

result:

ok single line: '3'

Test #19:

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

input:

48
1 6
2 6
2 5
3 5
3 6
5 6
5 3
8 3
8 2
9 2
9 3
12 3
12 1
15 1
15 6
16 6
16 8
20 8
20 5
22 5
22 3
23 3
23 5
25 5
25 2
28 2
28 5
27 5
27 4
26 4
26 6
24 6
24 9
23 9
23 7
22 7
22 11
18 11
18 10
17 10
17 9
14 9
14 7
10 7
10 5
7 5
7 10
1 10

output:

5

result:

ok single line: '5'

Test #20:

score: 0
Accepted
time: 11ms
memory: 167564kb

input:

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

output:

4

result:

ok single line: '4'

Test #21:

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

input:

1024
0 0
92 0
92 -49
107 -49
107 -93
200 -93
200 -107
229 -107
229 -161
269 -161
269 -218
316 -218
316 -246
389 -246
389 -269
418 -269
418 -299
514 -299
514 -355
601 -355
601 -377
688 -377
688 -396
744 -396
744 -418
849 -418
849 -432
905 -432
905 -481
918 -481
918 -492
1017 -492
1017 -538
1065 -538
...

output:

1

result:

ok single line: '1'

Test #22:

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

input:

80
-1 12
1 12
1 25
41 25
41 -10
43 -10
43 -8
53 -8
53 15
72 15
72 6
88 6
88 1
90 1
90 40
100 40
100 70
120 70
120 77
162 77
162 64
179 64
179 38
195 38
195 6
210 6
210 2
236 2
236 -6
238 -6
238 -2
250 -2
250 39
286 39
286 15
288 15
288 86
314 86
314 44
316 44
316 91
302 91
302 115
300 115
300 96
276...

output:

5

result:

ok single line: '5'

Test #23:

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

input:

400
-2 12
2 12
2 25
40 25
40 -10
44 -10
44 -8
54 -8
54 15
71 15
71 6
87 6
87 1
91 1
91 40
101 40
101 70
121 70
121 77
161 77
161 64
178 64
178 38
199 38
199 6
214 6
214 2
218 2
218 74
266 74
266 46
270 46
270 62
302 62
302 51
315 51
315 10
319 10
319 74
362 74
362 66
378 66
378 38
382 38
382 59
427 ...

output:

11

result:

ok single line: '11'

Test #24:

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

input:

2020
95 2322
582 2322
582 1435
592 1435
592 4400
1067 4400
1067 -98
1077 -98
1077 8325
2768 8325
2768 4616
2778 4616
2778 7611
4014 7611
4014 2550
4654 2550
4654 2080
4664 2080
4664 8987
5858 8987
5858 6974
6795 6974
6795 1648
6805 1648
6805 5148
6966 5148
6966 6895
8109 6895
8109 1904
8119 1904
811...

output:

35

result:

ok single line: '35'

Test #25:

score: 0
Accepted
time: 40ms
memory: 206384kb

input:

40000
-100005 2322
-99518 2322
-99518 1435
-99508 1435
-99508 4400
-99033 4400
-99033 -98
-99023 -98
-99023 8325
-97332 8325
-97332 4616
-97322 4616
-97322 7611
-96086 7611
-96086 2550
-95446 2550
-95446 2080
-95436 2080
-95436 8987
-94242 8987
-94242 6974
-93305 6974
-93305 1648
-93295 1648
-93295 ...

output:

723

result:

ok single line: '723'

Test #26:

score: 0
Accepted
time: 96ms
memory: 220688kb

input:

100000
-100005 2322
-99518 2322
-99518 1435
-99508 1435
-99508 4400
-99033 4400
-99033 -98
-99023 -98
-99023 8325
-97332 8325
-97332 4616
-97322 4616
-97322 7611
-96086 7611
-96086 2550
-95446 2550
-95446 2080
-95436 2080
-95436 8987
-94242 8987
-94242 6974
-93305 6974
-93305 1648
-93295 1648
-93295...

output:

1906

result:

ok single line: '1906'

Test #27:

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

input:

480
-99999905 2322
-99999418 2322
-99999418 1435
-99999408 1435
-99999408 4400
-99998933 4400
-99998933 -98
-99998923 -98
-99998923 8325
-99997232 8325
-99997232 4616
-99997222 4616
-99997222 7611
-99995986 7611
-99995986 2550
-99995346 2550
-99995346 2080
-99995336 2080
-99995336 8987
-99994142 898...

output:

12

result:

ok single line: '12'

Test #28:

score: 0
Accepted
time: 95ms
memory: 222452kb

input:

100000
-2 12
2 12
2 25
40 25
40 -10
44 -10
44 -8
54 -8
54 15
71 15
71 6
87 6
87 1
91 1
91 40
101 40
101 70
121 70
121 77
161 77
161 64
178 64
178 38
199 38
199 6
214 6
214 2
218 2
218 74
266 74
266 46
270 46
270 62
302 62
302 51
315 51
315 10
319 10
319 74
362 74
362 66
378 66
378 38
382 38
382 59
4...

output:

2624

result:

ok single line: '2624'

Test #29:

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

input:

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

output:

5

result:

ok single line: '5'

Test #30:

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

input:

16
1 1
3 1
3 4
12 4
12 8
19 8
19 10
16 10
16 12
14 12
14 14
8 14
8 9
5 9
5 7
1 7

output:

2

result:

ok single line: '2'

Test #31:

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

input:

20
1 4
4 4
4 2
5 2
5 5
6 5
6 4
8 4
8 1
10 1
10 2
11 2
11 3
9 3
9 6
7 6
7 9
2 9
2 5
1 5

output:

2

result:

ok single line: '2'

Test #32:

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

input:

20
1 4
4 4
4 2
5 2
5 6
6 6
6 4
8 4
8 1
10 1
10 2
11 2
11 3
9 3
9 6
7 6
7 9
2 9
2 5
1 5

output:

2

result:

ok single line: '2'

Test #33:

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

input:

20
1 4
4 4
4 2
5 2
5 7
6 7
6 4
8 4
8 1
10 1
10 2
11 2
11 3
9 3
9 6
7 6
7 9
2 9
2 5
1 5

output:

3

result:

ok single line: '3'

Test #34:

score: 0
Accepted
time: 4ms
memory: 162124kb

input:

22
1 4
4 4
4 2
5 2
5 6
6 6
6 5
7 5
7 4
8 4
8 1
10 1
10 2
11 2
11 3
9 3
9 6
7 6
7 9
2 9
2 5
1 5

output:

2

result:

ok single line: '2'

Test #35:

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

input:

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

output:

3

result:

ok single line: '3'

Test #36:

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

input:

24
0 80
10 80
10 50
20 50
20 40
30 40
30 20
40 20
40 10
50 10
50 0
60 0
60 20
50 20
50 30
40 30
40 60
30 60
30 70
20 70
20 100
10 100
10 90
0 90

output:

3

result:

ok single line: '3'

Test #37:

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

input:

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

output:

3

result:

ok single line: '3'