QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#312784#4270. Double Attendancexiaolang0 1ms7852kbC++142.2kb2024-01-24 12:01:462024-01-24 12:01:47

Judging History

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

  • [2024-01-24 12:01:47]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:7852kb
  • [2024-01-24 12:01:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int INF=1e9+9;
struct Node{
	int l,r;
}c[2][N];
double d[N][2][2];
bool cmp(Node x,Node y){
	return x.l<y.l;
}
int n1,n2,T;
int bel(double tim,bool op){
	int l=1,r=(!op)?n1:n2,ans=0;
	while(l<=r){
		int mid=l+r>>1;
		if(c[op][mid].r>=tim){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	return ans;
}
signed main(){
	scanf("%lld%lld%lld",&n1,&n2,&T);
	for(int i=1;i<=n1;i++){
		scanf("%lld%lld",&c[0][i].l,&c[0][i].r);
	}
	for(int i=1;i<=n2;i++){
		scanf("%lld%lld",&c[1][i].l,&c[1][i].r);
	}
	c[0][n1+1].l=c[0][n1+1].r=INF;
	c[1][n2+1].l=c[1][n2+1].r=INF;
	sort(c[0]+1,c[0]+n1+1,cmp);
	sort(c[1]+1,c[1]+n2+1,cmp);
	for(int i=0;i<=n1+n2;i++){
		d[i][0][0]=d[i][0][1]=d[i][1][0]=d[i][1][1]=INF;
	}
	d[0][0][0]=0.5;
	int max_x=0;
	for(int i=0;i<=n1+n2;i++){
		for(int j=0;j<=1;j++){
			for(int k=0;k<=1;k++){
				if(d[i][j][k]>=INF/2)continue;
				max_x=max(max_x,i);
				//cout<<i<<" "<<j<<" "<<k<<":"<<d[i][j][k]<<"\n";
				int tnow=bel(d[i][j][k],j);
				int ano=bel(d[i][j][k],j^1);
				bool flag=(c[j^1][ano].l<=d[i][j][k]&&d[i][j][k]<=c[j^1][ano].r&&k);
				bool flgg=(c[j][tnow].l<=d[i][j][k]&&d[i][j][k]<=c[j][tnow].r);
				int tt=bel(d[i][j][k]+T,j^1);
				//cout<<tt<<"\n";
				if(!tt)continue;
				if(flag&&(tt==ano)){
					bool flg=(bel(max(d[i][j][k]+T,c[j^1][tt+1].l+0.5),j)==tnow&&flgg);
					//if(i==3&&j==0&&flg)cout<<i<<" "<<j<<" "<<k<<"\n";
					d[i+1][j^1][flg]=min(d[i+1][j^1][flg],max(d[i][j][k]+T,c[j^1][tt+1].l+0.5));
				}
				else{
					bool flg=(bel(max(d[i][j][k]+T,c[j^1][tt].l+0.5),j)==tnow&&flgg);
					//if(i==3&&j==0&&flg)cout<<i<<" "<<j<<" "<<k<<"\n";
					d[i+1][j^1][flg]=min(d[i+1][j^1][flg],max(d[i][j][k]+T,c[j^1][tt].l+0.5));
				}
				if(tnow){
					//???
					if(flgg){
						double nxttim=c[j][tnow+1].l+0.5;
						bool fll=(bel(nxttim,j^1)==ano&&flag);
						d[i+1][j][fll]=min(d[i+1][j][fll],nxttim);
					}
					else{
						double nxttim=c[j][tnow].l+0.5;
						bool fll=(bel(nxttim,j^1)==ano&&flag);
						d[i+1][j][fll]=min(d[i+1][j][fll],nxttim);	
					}
				}
			}
		}
	}
	cout<<max_x<<"\n";
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 1ms
memory: 7840kb

input:

3 1 8
10 20
100 101
20 21
15 25

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7728kb

input:

1 5 3
1 100
1 2
2 3
3 4
4 5
5 6

output:

4

result:

ok single line: '4'

Test #3:

score: -5
Wrong Answer
time: 0ms
memory: 7852kb

input:

10 10 5
4 9
43 48
69 70
70 72
52 67
75 83
100 103
103 1501
10 27
28 40
5 7
27 29
30 39
40 42
42 45
67 80
0 5
45 59
10 20
22 23

output:

16

result:

wrong answer 1st lines differ - expected: '18', found: '16'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #104:

score: 0
Wrong Answer
time: 1ms
memory: 7756kb

input:

1 1 1
0 1
0 1

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%