QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#36007#4270. Double AttendanceY25t0 3ms3768kbC++20908b2022-06-22 10:54:532022-06-22 10:54:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-22 10:54:55]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:3768kb
  • [2022-06-22 10:54:53]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long

int n[2],k;
std::set<std::pair<int,int>> s[2];

inline std::set<std::pair<int,int>>::iterator fnd(int o,int x){
	return s[o].lower_bound({x+1,0});
}

std::unordered_map<ll,int> f;
inline int dfs(int x,int o,int t){
	ll _=(ll)x<<2|o<<1|t;
	if(f.count(_))
		return f[_];
	int res=0;
	auto u=std::prev(fnd(o^1,x)),v=fnd(o,x);
	if(v!=s[o].end())
		res=std::max(res,dfs(v->first,o,std::prev(fnd(o^1,v->first))==u?t:0)+1);
	auto w=std::prev(fnd(o^1,x+k));
	if(w->second<x+k||(t&&w==u))
		w++;
	if(w!=s[o^1].end()){
		int y=std::max(x+k,w->first);
		res=std::max(res,dfs(y,o^1,fnd(o,y)==v)+1);
	}
	return f[_]=res;
}

int main(){
	scanf("%d%d%d",&n[0],&n[1],&k);
	s[0].emplace(-1,-1),s[1].emplace(-1,-1);
	for(int i=1;i<=n[0]+n[1];i++){
		int l,r;
		scanf("%d%d",&l,&r);
		s[i>n[0]].emplace(l,r-1);
	}
	printf("%d\n",dfs(0,0,0));
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 2ms
memory: 3660kb

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: 2ms
memory: 3704kb

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: 3724kb

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: 2ms
memory: 3660kb

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: 3ms
memory: 3768kb

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%