QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#311782#4270. Double AttendanceC1942huangjiaxu0 2ms13268kbC++141.3kb2024-01-22 19:27:002024-01-22 19:27:01

Judging History

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

  • [2024-01-22 19:27:01]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:13268kb
  • [2024-01-22 19:27:00]
  • 提交

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]=-1;
	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: 13268kb

input:

3 1 8
10 20
100 101
20 21
15 25

output:

3

result:

ok single line: '3'

Test #2:

score: -5
Wrong Answer
time: 2ms
memory: 13200kb

input:

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

output:

5

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #104:

score: 6
Accepted
time: 0ms
memory: 13204kb

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #105:

score: -6
Wrong Answer
time: 0ms
memory: 13172kb

input:

1 2000 2
999999996 1000000000
336 337
502 503
1906 1907
963 964
1351 1352
1795 1796
1510 1511
304 305
1930 1931
1735 1736
1469 1470
338 339
813 814
182 183
209 210
321 322
849 850
721 722
394 395
889 890
1758 1759
1440 1441
560 561
1470 1471
1916 1917
793 794
1366 1367
158 159
1602 1603
214 215
1119...

output:

2001

result:

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

Subtask #4:

score: 0
Skipped

Dependency #1:

0%