QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#36139 | #4270. Double Attendance | momoLRS | 0 | 10ms | 32084kb | C++ | 3.6kb | 2022-06-24 16:12:43 | 2022-06-24 16:12:44 |
Judging History
answer
#include<bits/stdc++.h>
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define int long long
#define mod (1000000007)
// int mod;
#ifndef ONLINE_JUDGE
#pragma GCC optimize(2)
#endif
using namespace std;
namespace IO{
inline int read(){
int n=0;
int s=1;
char x;
while((x=getchar())<'0'||x>'9')
if(x=='-')
s=-1;
while(x>='0'&&x<='9'){
n=(n<<1)+(n<<3)+(x^48),
x=getchar();
}
return n*s;
}
void write(char x){
putchar(x);
}
void write(const char *x){
for(;*x;++x)
putchar(*x);
}
void write(char *x){
for(;*x;++x)
putchar(*x);
}
void write(signed x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar('0'+x-x/10*10);
}
void write(long long x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar('0'+x-x/10*10);
}
void write(double x){
printf("%lf",x);
}
template<typename type1,typename type2,typename ...typen>
void write(type1 a1,type2 a2,typen ...an){
write(a1);
write(a2,an...);
}
}// namespace IO
inline long long max(long long a,long long b){return a>b?a:b;}
inline long long min(long long a,long long b){return a>b?b:a;}
inline signed max(signed a,signed b){return a>b?a:b;}
inline signed min(signed a,signed b){return a>b?b:a;}
// stop
struct Node{
int l,r;
bool operator<(Node x)const{
return l<x.l;
}
}cl1[300001],cl2[300001];
map<int,int>mem[300001][2];
// #define wtf
signed main(){
using namespace IO;
// define int long long
// mod = 1000000007
#ifdef wtf
string filename="name";
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
#endif
int n=read()+1,m=read(),k=read();
cl1[1].l=0,cl1[1].r=1;
for(int i=2;i<=n;i++){
cl1[i].l=read(),cl1[i].r=read();
}
sort(cl1+1,cl1+n+1);
for(int i=1;i<=m;i++){
cl2[i].l=read(),cl2[i].r=read();
}
sort(cl2+1,cl2+m+1);
int pos1=1,pos2=1;
int ans=-1;
mem[1][0][0]=0;
for(int i=1,j=1;i<=n||j<=m;){
if(j>m||(i<=n&&cl1[i].l<=cl2[j].l)){
int maxm=-1;
for(auto x:mem[i][0]){
// cout<<0<<" "<<x.first<<" "<<x.second<<"\n";
assert(x.first<cl1[i].r);
maxm=max(maxm,x.second);
while(pos2<=m&&cl2[pos2].r<=x.first+k)pos2++;
if(pos2>m)continue;
int t=max(cl2[pos2].l,x.first+k);
if(t>=cl2[pos2].r)assert(0);
mem[pos2][1][t]=max(mem[pos2][1][t],x.second+1);
}
ans=max(ans,maxm);
if(maxm!=-1&&i<n)mem[i+1][0][cl1[i+1].l]=max(mem[i+1][0][cl1[i+1].l],maxm+1);
i++;
pos1=max(pos1,i);
}
else {
int maxm=-1;
for(auto x:mem[j][1]){
assert(x.first<cl2[j].r);
// cout<<1<<" "<<x.first<<" "<<x.second<<"\n";
maxm=max(maxm,x.second);
while(pos1<=n&&cl1[pos1].r<=x.first+k)pos1++;
if(pos1>n)continue;
int t=max(cl1[pos1].l,x.first+k);
if(t>=cl1[pos1].r)assert(0);
mem[pos1][0][t]=max(mem[pos1][0][t],x.second+1);
}
ans=max(maxm,ans);
if(maxm!=-1&&j<m)mem[j+1][1][cl2[j+1].l]=max(mem[j+1][1][cl2[j+1].l],maxm+1);
j++;
pos2=max(pos2,j);
}
}
write(ans);
return 0;
}
/*
---- ----
---- ----
---- ----
---- ----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
---- ----
---- ----
---- ----
---- ----
----------------------------------------
*/
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 3ms
memory: 31712kb
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: 31788kb
input:
1 5 3 1 100 1 2 2 3 3 4 4 5 5 6
output:
3
result:
wrong answer 1st lines differ - expected: '4', found: '3'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #104:
score: 6
Accepted
time: 4ms
memory: 31684kb
input:
1 1 1 0 1 0 1
output:
1
result:
ok single line: '1'
Test #105:
score: 0
Accepted
time: 10ms
memory: 31932kb
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:
2000
result:
ok single line: '2000'
Test #106:
score: 0
Accepted
time: 3ms
memory: 32084kb
input:
2000 2000 249875 608195750 608695500 88455750 88955500 579210250 579710000 817091250 817591000 527736000 528235750 52473750 52973500 89955000 90454750 184407750 184907500 668165750 668665500 24487750 24987500 466266750 466766500 471764000 472263750 212393750 212893500 250874500 251374250 939530000 9...
output:
4000
result:
ok single line: '4000'
Test #107:
score: 0
Accepted
time: 8ms
memory: 32012kb
input:
2000 2000 249875 965017250 965517000 73963000 74462750 242878500 243378250 148925500 149425250 747126250 747626000 384307750 384807500 655172250 655672000 278360750 278860500 899050250 899550000 496251750 496751500 92953500 93453250 677661000 678160750 828085750 828585500 297351250 297851000 5887055...
output:
4000
result:
ok single line: '4000'
Test #108:
score: -6
Wrong Answer
time: 7ms
memory: 32004kb
input:
2000 2000 499500 428 429 764235000 765234000 511488000 512487000 291 292 585414000 586413000 127 128 819 820 727 728 233766000 234765000 643 644 234 235 326 327 432 433 218781000 219780000 10989000 11988000 805194000 806193000 283716000 284715000 965034000 966033000 632367000 633366000 824 825 454 4...
output:
3998
result:
wrong answer 1st lines differ - expected: '4000', found: '3998'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%