QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#311781#4270. Double AttendanceC1942huangjiaxu0 0ms13244kbC++141.3kb2024-01-22 19:26:232024-01-22 19:26:23

Judging History

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

  • [2024-01-22 19:26:23]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:13244kb
  • [2024-01-22 19:26:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5,inf=1e9+7;
int n0,n1,K,f[N][2][2],ans;
vector<pair<int,int> >p[2];
inline void U(int &x,int y){
	x=x>y?y:x;
}
int main(){
	scanf("%d%d%d",&n0,&n1,&K);
	for(int i=1,x,y;i<=n0;++i){
		scanf("%d%d",&x,&y);
		p[0].emplace_back(x,y);
	}
	for(int i=1,x,y;i<=n1;++i){
		scanf("%d%d",&x,&y);
		p[1].emplace_back(x,y);
	}
	sort(p[0].begin(),p[0].end());
	sort(p[1].begin(),p[1].end());
	memset(f,0x3f,sizeof(f));
	f[0][0][0]=0;
	for(int i=0;i<=n0+n1;++i)for(int j=0;j<2;++j)for(int k=0;k<2;++k)if(f[i][j][k]<inf){
		ans=i;
		int t=f[i][j][k],w;
		int u=upper_bound(p[j].begin(),p[j].end(),make_pair(t,inf))-p[j].begin()-1,v=upper_bound(p[j^1].begin(),p[j^1].end(),make_pair(t,inf))-p[j^1].begin()-1;
		if(u+1<p[j].size()){
			w=p[j][u+1].first;
			if(v>=0&&p[j^1][v].second>w)U(f[i+1][j][k],w);
			else U(f[i+1][j][0],w);
		}
		if(t+K<inf){
			int o=upper_bound(p[j^1].begin(),p[j^1].end(),make_pair(t+K,inf))-p[j^1].begin()-1;
			if(o<0||k&&o==v||p[j^1][o].second<=t+K)++o;
			if(o<p[j^1].size()&&p[j^1][o].second>t+K){
				w=max(p[j^1][o].first,t+K);
				int z=upper_bound(p[j].begin(),p[j].end(),make_pair(w,inf))-p[j].begin()-1;
				U(f[i+1][j^1][z==u],w);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 0ms
memory: 13120kb

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

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: 0
Accepted
time: 0ms
memory: 13156kb

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:

18

result:

ok single line: '18'

Test #4:

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

input:

1 1 1
0 1
0 1

output:

0

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #104:

score: 0
Wrong Answer
time: 0ms
memory: 13224kb

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%