QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#36007 | #4270. Double Attendance | Y25t | 0 | 3ms | 3768kb | C++20 | 908b | 2022-06-22 10:54:53 | 2022-06-22 10:54:55 |
Judging History
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%