QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618069#1962. Security SystemAfterlifeAC ✓53ms41120kbC++205.0kb2024-10-06 18:30:262024-10-06 18:30:30

Judging History

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

  • [2024-10-06 18:30:30]
  • 评测
  • 测评结果:AC
  • 用时:53ms
  • 内存:41120kb
  • [2024-10-06 18:30:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e5+1e3+7;
const int inf=0x3f3f3f3f;

int n,m,l[N],r[N];

int il[N],ir[N],dl[N],dr[N];

struct P{
    int x,y;
}p[N];

int mxl[N][21],mnr[N][21];

int qmxl(int l,int r)
{
    int k=__lg(r-l+1);
    return max(mxl[l][k],mxl[r-(1<<k)+1][k]);
}

int qmnr(int l,int r)
{
    int k=__lg(r-l+1);
    return min(mnr[l][k],mnr[r-(1<<k)+1][k]);
}

int a[N],b[N],c[N];

int gl[N],gr[N];
int f[N],g[N];

int qlp(int x,int w)//[x...n], l[i]>w min(i)
{
    int l=x-1,r=n+1;
    while(r-l>1)
    {
        int mid=(l+r)>>1;
        if(qmxl(x,mid)>w)
            r=mid;
        else
            l=mid;
    }
    return r;
}

int qrp(int x,int w)//[x..n] r[i]<w min(i)
{
    int l=x-1,r=n+1;
    while(r-l>1)
    {
        int mid=(l+r)>>1;
        if(qmnr(x,mid)<w)
            r=mid;
        else
            l=mid;
    }
    return r;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    vector<int> V;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].x>>p[i].y;
        V.push_back(p[i].y);
    }
    sort(V.begin(),V.end());
    for(int i=1;i<=n;i++)
        p[i].y=lower_bound(V.begin(),V.end(),p[i].y)-V.begin()+1;
    map<int,vector<int> >v;
    for(int i=1;i<=n;i++)
    {
        int j=i<n?i+1:1;
        if(p[i].y==p[j].y)
        {
            int L=min(p[i].x,p[j].x),R=max(p[i].x,p[j].x);
            v[L].push_back(p[i].y);
            v[R].push_back(-p[i].y);
        }
        else
            continue;
    }
    multiset<int> ms;
    m=0;
    for(auto [x,ys]:v)
    {
        for(auto y:ys)
            if(y>0)
                ms.insert(y);
        for(auto y:ys)
            if(y<0)
                ms.erase(ms.find(-y));
        assert(ms.size()==2||ms.size()==0);
        if(!ms.size())
            break;
        ++m;
        l[m]=*ms.begin();
        r[m]=*(next(ms.begin()));
    }
    // cout<<endl;
    // for(int i=1;i<=m;i++)
    //     cout<<l[i]<<" "<<r[i]<<endl;
    //end of prelude
    n=m;
    for(int i=1;i<=n;i++)
        mxl[i][0]=l[i],mnr[i][0]=r[i];
    for(int j=1;j<=20;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            mxl[i][j]=max(mxl[i][j-1],mxl[i+(1<<(j-1))][j-1]);
            mnr[i][j]=min(mnr[i][j-1],mnr[i+(1<<(j-1))][j-1]);
        }
    for(int i=1;i<=n;i++)
    {
        int l=i,r=n+1;
        while(r-l>1)
        {
            int mid=(l+r)>>1;
            if(qmxl(i,mid)<qmnr(i,mid))
                l=mid;
            else
                r=mid;
        }
        a[i]=l;
    }
    il[n]=dr[n]=b[n]=n;
    for(int i=n-1;i>=1;i--)
    {
        il[i]=(l[i]<=l[i+1]?il[i+1]:i);
        dr[i]=(r[i]>=r[i+1]?dr[i+1]:i);
        b[i]=min(il[i],dr[i]);
    }
    dl[n]=ir[n]=c[n]=n;
    for(int i=n-1;i>=1;i--)
    {
        dl[i]=(l[i]>=l[i+1]?dl[i+1]:i);
        ir[i]=(r[i]<=r[i+1]?ir[i+1]:i);
        c[i]=min(dl[i],ir[i]);
    }

    l[n+1]=1e9,r[n+1]=-1e9;

    #define ckmin(x,y) (x)=min((x),(y))
    memset(f,0x3f,sizeof(f));
    memset(g,0x3f,sizeof(g));
    int ans=inf;
    f[0]=0;
    // for(int i=1;i<=n;++i){
    //     cerr<<" i: "<<i<<" "<<l[i]<<' '<<r[i]<<" a: "<<a[i]<<" b: "<<b[i]<<" c: "<<c[i]<<endl;
    // }
    for(int i=0;i<=n;++i){
        if(i==n){
            ans=min(ans,f[i]);
            ans=min(ans,g[i]);
            break;
        }
        if(b[i]==n){
            ans=min(ans,g[i]);
        }
        else{
            ckmin(f[a[b[i]+1]],g[i]+1);
            if(b[i]+1==n){
                ans=min(ans,g[i]+1);
            }
            else{
                //no
                int L,R;
                if(l[b[i]+1]<l[b[i]]&&r[b[i]+1]>r[b[i]]){
                    L=l[b[i]+1];
                    R=r[b[i]+1];
                    if(!(l[b[i]+2]<=L&&r[b[i]+2]>=R)){
                        ckmin(g[b[i]+1],g[i]+1);
                    }
                    else{
                        ckmin(g[c[b[i]+2]],g[i]+1);
                    }
                }
                else if(r[b[i]+1]>r[b[i]]){
                    int z=n;
                    z=min(z,ir[b[i]+1]);
                    z=min(z,qlp(b[i]+1,r[b[i]])-1);
                    z=min(z,c[min(n,il[b[i]+1]+1)]);
                    ckmin(g[z],g[i]+1);
                    // if(i==3){
                    //     cerr<<" z: "<<z<<" "<<ir[b[i]+1]<<" "<<qlp(b[i]+1,r[b[i]])-1<<" "<<c[min(n,il[b[i]+1]+1)]<<endl;
                    // }
                }
                else{
                    int z=n;
                    z=min(z,dl[b[i]+1]);
                    z=min(z,qrp(b[i]+1,l[b[i]])-1);
                    z=min(z,c[min(n,dr[b[i]+1]+1)]);
                    ckmin(g[z],g[i]+1);
                }
            }
        }
        ckmin(f[a[i+1]],f[i]+1);
        ckmin(g[c[i+1]],f[i]+1);
    }
    ans=min(ans,f[n+1]);
    ans=min(ans,g[n+1]);
    ans=max(ans,1ll);
    cout<<ans<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 19028kb

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

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: 0ms
memory: 18240kb

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

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: 0ms
memory: 18244kb

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: 0ms
memory: 19116kb

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

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: 0ms
memory: 18148kb

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: 0ms
memory: 17256kb

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: 0ms
memory: 19276kb

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

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: 43ms
memory: 41120kb

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: 3ms
memory: 18276kb

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: 0ms
memory: 18780kb

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: 0ms
memory: 19528kb

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: 0ms
memory: 17288kb

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: 0ms
memory: 18228kb

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: 0ms
memory: 18140kb

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: 0ms
memory: 18476kb

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: 2ms
memory: 19604kb

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

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: 0ms
memory: 19032kb

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

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: 13ms
memory: 24136kb

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: 41ms
memory: 36716kb

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: 0ms
memory: 19272kb

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: 53ms
memory: 37016kb

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

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: 0ms
memory: 19532kb

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

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: 0ms
memory: 18192kb

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: 0ms
memory: 18312kb

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: 0ms
memory: 18184kb

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: 0ms
memory: 17608kb

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

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

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'