QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311782 | #4270. Double Attendance | C1942huangjiaxu | 0 | 2ms | 13268kb | C++14 | 1.3kb | 2024-01-22 19:27:00 | 2024-01-22 19:27:01 |
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]=-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%