QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#312784 | #4270. Double Attendance | xiaolang | 0 | 1ms | 7852kb | C++14 | 2.2kb | 2024-01-24 12:01:46 | 2024-01-24 12:01:47 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int INF=1e9+9;
struct Node{
int l,r;
}c[2][N];
double d[N][2][2];
bool cmp(Node x,Node y){
return x.l<y.l;
}
int n1,n2,T;
int bel(double tim,bool op){
int l=1,r=(!op)?n1:n2,ans=0;
while(l<=r){
int mid=l+r>>1;
if(c[op][mid].r>=tim){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
signed main(){
scanf("%lld%lld%lld",&n1,&n2,&T);
for(int i=1;i<=n1;i++){
scanf("%lld%lld",&c[0][i].l,&c[0][i].r);
}
for(int i=1;i<=n2;i++){
scanf("%lld%lld",&c[1][i].l,&c[1][i].r);
}
c[0][n1+1].l=c[0][n1+1].r=INF;
c[1][n2+1].l=c[1][n2+1].r=INF;
sort(c[0]+1,c[0]+n1+1,cmp);
sort(c[1]+1,c[1]+n2+1,cmp);
for(int i=0;i<=n1+n2;i++){
d[i][0][0]=d[i][0][1]=d[i][1][0]=d[i][1][1]=INF;
}
d[0][0][0]=0.5;
int max_x=0;
for(int i=0;i<=n1+n2;i++){
for(int j=0;j<=1;j++){
for(int k=0;k<=1;k++){
if(d[i][j][k]>=INF/2)continue;
max_x=max(max_x,i);
//cout<<i<<" "<<j<<" "<<k<<":"<<d[i][j][k]<<"\n";
int tnow=bel(d[i][j][k],j);
int ano=bel(d[i][j][k],j^1);
bool flag=(c[j^1][ano].l<=d[i][j][k]&&d[i][j][k]<=c[j^1][ano].r&&k);
bool flgg=(c[j][tnow].l<=d[i][j][k]&&d[i][j][k]<=c[j][tnow].r);
int tt=bel(d[i][j][k]+T,j^1);
//cout<<tt<<"\n";
if(!tt)continue;
if(flag&&(tt==ano)){
bool flg=(bel(max(d[i][j][k]+T,c[j^1][tt+1].l+0.5),j)==tnow&&flgg);
//if(i==3&&j==0&&flg)cout<<i<<" "<<j<<" "<<k<<"\n";
d[i+1][j^1][flg]=min(d[i+1][j^1][flg],max(d[i][j][k]+T,c[j^1][tt+1].l+0.5));
}
else{
bool flg=(bel(max(d[i][j][k]+T,c[j^1][tt].l+0.5),j)==tnow&&flgg);
//if(i==3&&j==0&&flg)cout<<i<<" "<<j<<" "<<k<<"\n";
d[i+1][j^1][flg]=min(d[i+1][j^1][flg],max(d[i][j][k]+T,c[j^1][tt].l+0.5));
}
if(tnow){
//???
if(flgg){
double nxttim=c[j][tnow+1].l+0.5;
bool fll=(bel(nxttim,j^1)==ano&&flag);
d[i+1][j][fll]=min(d[i+1][j][fll],nxttim);
}
else{
double nxttim=c[j][tnow].l+0.5;
bool fll=(bel(nxttim,j^1)==ano&&flag);
d[i+1][j][fll]=min(d[i+1][j][fll],nxttim);
}
}
}
}
}
cout<<max_x<<"\n";
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 1ms
memory: 7840kb
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: 1ms
memory: 7728kb
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: -5
Wrong Answer
time: 0ms
memory: 7852kb
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:
16
result:
wrong answer 1st lines differ - expected: '18', found: '16'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #104:
score: 0
Wrong Answer
time: 1ms
memory: 7756kb
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%