QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311781 | #4270. Double Attendance | C1942huangjiaxu | 0 | 0ms | 13244kb | C++14 | 1.3kb | 2024-01-22 19:26:23 | 2024-01-22 19:26:23 |
Judging History
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%