QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#126546#4193. Joined SessionszhichengWA 2ms7344kbC++142.0kb2023-07-18 16:51:222023-07-18 16:51:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-18 16:51:26]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7344kb
  • [2023-07-18 16:51:22]
  • 提交

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");
}

Details

Tip: Click on the bar to expand more detailed information

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'