QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #618133 | #4270. Double Attendance | Idtwtei | 0 | 1ms | 5948kb | C++14 | 1.8kb | 2024-10-06 19:02:33 | 2024-10-06 19:02:34 |
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;
ans=max(ans,(int)!a[0][1][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
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 5900kb
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: 5948kb
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: 1ms
memory: 5888kb
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
Accepted
time: 1ms
memory: 5936kb
input:
1 1 1 0 1 0 1
output:
1
result:
ok single line: '1'
Test #5:
score: 5
Accepted
time: 1ms
memory: 5888kb
input:
1 10 2 1 2000 4 5 10 11 7 8 3 4 9 10 1 2 2 3 8 9 6 7 5 6
output:
10
result:
ok single line: '10'
Test #6:
score: 5
Accepted
time: 1ms
memory: 5888kb
input:
10 10 90 1440 1620 0 180 1080 1260 900 1080 180 360 720 900 540 720 360 540 1620 1800 1260 1440 1170 1350 990 1170 1530 1710 1350 1530 90 270 450 630 270 450 630 810 810 990 1710 1890
output:
20
result:
ok single line: '20'
Test #7:
score: 5
Accepted
time: 1ms
memory: 5900kb
input:
10 10 90 1080 1260 1440 1620 900 1080 1620 1800 180 360 360 540 540 720 1800 1980 1260 1440 720 900 90 270 1710 1890 810 990 1170 1350 1530 1710 630 810 1350 1530 990 1170 450 630 270 450
output:
20
result:
ok single line: '20'
Test #8:
score: 5
Accepted
time: 1ms
memory: 5880kb
input:
10 10 166 1 2 664 996 332 664 1660 1992 0 1 1328 1660 996 1328 3 4 2 3 4 5 333 334 1494 1826 498 830 1162 1494 334 335 336 337 0 332 830 1162 335 336 332 333
output:
20
result:
ok single line: '20'
Test #9:
score: 5
Accepted
time: 1ms
memory: 5824kb
input:
10 10 166 2 3 0 1 3 4 1328 1660 1999 2000 996 1328 1 2 332 664 4 5 664 996 334 335 335 336 333 334 1162 1494 0 332 498 830 336 337 830 1162 332 333 1999 2000
output:
19
result:
ok single line: '19'
Test #10:
score: 0
Wrong Answer
time: 1ms
memory: 5884kb
input:
10 10 1 1607 1721 327 413 222 264 1744 1746 35 50 619 766 995 1127 1421 1541 1236 1294 984 995 626 1122 1313 1386 65 141 1394 1428 1553 1764 1766 1990 1551 1552 465 531 1500 1531 623 625
output:
15
result:
wrong answer 1st lines differ - expected: '20', found: '15'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #104:
score: 6
Accepted
time: 1ms
memory: 5892kb
input:
1 1 1 0 1 0 1
output:
1
result:
ok single line: '1'
Test #105:
score: 0
Wrong Answer
time: 1ms
memory: 5832kb
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:
1999
result:
wrong answer 1st lines differ - expected: '2000', found: '1999'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%