QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#725427 | #1962. Security System | ucup-team3161# | AC ✓ | 96ms | 223472kb | C++17 | 5.6kb | 2024-11-08 17:41:30 | 2024-11-08 17:41:30 |
Judging History
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;
}
/*
*/
详细
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'