QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#126546 | #4193. Joined Sessions | zhicheng | WA | 2ms | 7344kb | C++14 | 2.0kb | 2023-07-18 16:51:22 | 2023-07-18 16:51:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int p[200010],las[100010],con[100010],s[400010],dp[100010][4];
struct s{
int l,r;
bool operator<(s a){
if(l!=a.l){
return l<a.l;
}
return r<a.r;
}
}a[100010];
int m(int x,int y,int p){
if(p==1){
return max(x,y);
}
return min(x,y);
}
void update(int x,int y,int l,int r,int rt,int w){
int mid=(l+r)>>1;
if(l==r){
s[rt]=m(s[rt],y,w);
return;
}
if(x<=mid){
update(x,y,l,mid,rt<<1,w);
}
else{
update(x,y,mid+1,r,rt<<1|1,w);
}
s[rt]=m(s[rt<<1],s[rt<<1|1],w);
}
int query(int x,int y,int l,int r,int rt,int w){
int mid=(l+r)>>1,ans=w?0:1e9;
if(x<=l&&y>=r){
return s[rt];
}
if(x<=mid){
ans=m(ans,query(x,y,l,mid,rt<<1,w),w);
}
if(y>=mid+1){
ans=m(ans,query(x,y,mid+1,r,rt<<1|1,w),w);
}
return ans;
}
int main(){
int n,w=0,tot=0,pos;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].l,&a[i].r);
p[++tot]=a[i].l;
p[++tot]=a[i].r;
}
sort(a+1,a+n+1);
sort(p+1,p+tot+1);
tot=unique(p+1,p+tot+1)-p-1;
for(int i=1;i<=n;i++){
a[i].l=lower_bound(p+1,p+tot+1,a[i].l)-p;
a[i].r=lower_bound(p+1,p+tot+1,a[i].r)-p;
if(a[i].l<=a[i-1].r){
w=1;
}
}
if(!w){
printf("impossible");
return 0;
}
for(int i=1;i<=n;i++){
if(a[i].l!=1){
las[i]=query(1,a[i].l-1,1,tot,1,1);
}
update(a[i].r,i,1,tot,1,1);
}
for(int i=1;i<=4*tot;i++){
s[i]=tot+1;
}
for(int i=1;i<=n;i++){
con[i]=query(a[i].l,tot,1,tot,1,0);
update(a[i].r,i,1,tot,1,0);
if(con[i]==n+1){
con[i]=i;
}
}
memset(dp,127,sizeof(dp));
for(int j=0;j<=3;j++){
for(int i=1;i<=n;i++){
if(!las[i]){
dp[i][j]=1;
}
else{
pos=i;
for(int k=0;k<=j;k++){
pos=con[pos];
if(!las[pos]){
dp[i][j]=1;
break;
}
dp[i][j]=min(dp[i][j],dp[las[pos]][j-k]+1);
}
}
}
}
for(int i=1;i<=3;i++){
if(dp[n][i]<dp[n][0]){
printf("%d",i);
return 0;
}
}
printf("impossible");
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7336kb
input:
4 1 3 2 5 4 7 6 9
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5748kb
input:
5 1 3 4 7 8 10 2 5 6 9
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 7208kb
input:
3 1 2 2 3 3 4
output:
impossible
result:
ok single line: 'impossible'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5880kb
input:
6 1 3 2 5 4 7 6 9 8 11 10 12
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 2ms
memory: 7344kb
input:
8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
output:
2
result:
ok single line: '2'
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 5220kb
input:
5 1 2 2 3 3 4 5 6 6 7
output:
1
result:
wrong answer 1st lines differ - expected: 'impossible', found: '1'