QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #618129 | #4270. Double Attendance | Idtwtei | 0 | 1ms | 5856kb | C++14 | 1.8kb | 2024-10-06 19:01:12 | 2024-10-06 19:01:13 |
answer
#include<bits/stdc++.h>
using namespace std;
#define ar(x) array<int,x>
const int N=3e5+100,INF=1e9;
inline int chkmin(int &x,int y){ return y<x?x=y,1:0; }
#define gc getchar()
#define rd read()
inline int read(){
int x=0,f=0; char c=gc;
for(;c<'0'||c>'9';c=gc) f|=(c=='-');
for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
int n[2],m,ans=0,f[2][2][2]; ar(2) a[2][N];
inline int ask(int op,int x){
int p=upper_bound(a[op]+1,a[op]+n[op]+1,ar(2){x,INF})-a[op]-1;
if(x<a[op][p][0]||a[op][p][1]<x) return 0; return p;
}
inline int nxt(int op,int x){
int p=upper_bound(a[op]+1,a[op]+n[op]+1,ar(2){x,INF})-a[op]-1;
if(x<a[op][p][0]||a[op][p][1]<x) return 0; return p+1<=n[op]?p+1:0;
}
int main(){
n[0]=rd,n[1]=rd,m=rd;
for(int i=1;i<=n[0];++i) a[0][i]={rd,rd-1}; sort(a[0]+1,a[0]+n[0]+1);
for(int i=1;i<=n[1];++i) a[1][i]={rd,rd-1}; sort(a[1]+1,a[1]+n[1]+1);
for(int x:{0,1}) for(int y:{0,1}) for(int z:{0,1}) f[x][y][z]=INF; f[!a[0][1][0]][0][0]=0;
for(int i=(!a[0][1][0])+1;i<=n[0]+n[1];++i){
for(int x:{0,1}) for(int y:{0,1}) f[i&1][x][y]=INF;
for(int x:{0,1}) for(int y:{0,1}){
if(f[i&1^1][x][y]==INF) continue;
int cur=f[i&1^1][x][y],v1=ask(x,cur),v2=ask(x^1,cur+m);
chkmin(f[i&1^(!v2||y)][x^1][v1&&ask(x,cur+2*m)==v1],cur+m); v1=nxt(x,cur);
if(v1) chkmin(f[i&1][x][v2&&y&&ask(x^1,a[x][v1][0]+m)==v2],a[x][v1][0]);
}
for(int x:{0,1}) for(int y:{0,1}){
if(f[i&1^1][x][y]==INF) continue;
int cur=f[i&1^1][x][y],v1=ask(x,cur),v2=ask(x^1,cur+m);
chkmin(f[i&1^(!v2||y)][x^1][v1&&ask(x,cur+2*m)==v1],cur+m); v1=nxt(x,cur);
if(v1) chkmin(f[i&1][x][v2&&y&&ask(x^1,a[x][v1][0]+m)==v2],a[x][v1][0]);
}
for(int x:{0,1}) for(int y:{0,1}) if(f[i&1][x][y]!=INF) ans=max(ans,i);
}
printf("%d\n", ans);
return 0;
}
// 17:48 - 18:29 - 18:57
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 1ms
memory: 5800kb
input:
3 1 8 10 20 100 101 20 21 15 25
output:
3
result:
ok single line: '3'
Test #2:
score: 5
Accepted
time: 1ms
memory: 5856kb
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
Accepted
time: 0ms
memory: 5816kb
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: 0
Wrong Answer
time: 1ms
memory: 5796kb
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: 1ms
memory: 5784kb
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%