QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#176338 | #5378. 匹配问题 | Xun_xiaoyao | 0 | 2ms | 16076kb | C++14 | 2.0kb | 2023-09-11 15:43:32 | 2023-09-11 15:43:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
int lim;
#define ls (pos<<1)
#define rs (pos<<1|1)
#define mid (l+r>>1)
int s[2000010],laz[2000010];
void giv_laz(int pos,int num){s[pos]+=num,laz[pos]+=num;}
void pushdown(int pos){if(laz[pos]) giv_laz(ls,laz[pos]),giv_laz(rs,laz[pos]),laz[pos]=0;}
void update(int pos){s[pos]=min(s[ls],s[rs]);}
void range_add(int L,int R,int num,int pos=1,int l=1,int r=lim)
{
if(L<=l&&r<=R) return giv_laz(pos,num);
if(r<L||R<l) return;
return pushdown(pos),range_add(L,R,num,ls,l,mid),range_add(L,R,num,rs,mid+1,r),update(pos);
}
int range_min(int L,int R,int pos=1,int l=1,int r=lim)
{
if(L<=l&&r<=R) return s[pos];
if(r<L||R<l) return 20070610;
return pushdown(pos),min(range_min(L,R,ls,l,mid),range_min(L,R,rs,mid+1,r));
}
#undef ls
#undef rs
#undef mid
int n,la,lb,x,y,ans;
int a[500010],b[500010];
typedef pair<int,int> pr;
set<pr> B;
int main()
{
n=Qread(),la=Qread(),lb=Qread();
for(int i=1;i<=n;i++) a[i]=Qread();
for(int i=1;i<=n;i++) b[i]=Qread();
sort(a+1,a+n+1),sort(b+1,b+n+1);
lim=max(b[n],a[n]+la);
for(int i=1;i<=n;i++) B.insert(make_pair(b[i],i));
for(int i=1;i<=n;i++) range_add(1,a[i]+la,1);
for(int i=1;i<=n;i++) range_add(1,b[i],-1);
for(int i=n;i;i--)
{
auto it=B.upper_bound(make_pair(a[i]+la,n));
it--;x=(*it).second;
it=B.upper_bound(make_pair(a[i]+lb,n));
if(it!=B.begin()){it--;y=(*it).second;}
else y=0;
if(b[y]>=a[i]&&range_min(b[y]+1,lim)>0)
{
ans++;
range_add(1,a[i]+la,-1);
range_add(1,b[y],1);
B.erase(B.find(make_pair(b[y],y)));
}
else
{
range_add(1,a[i]+la,-1);
range_add(1,b[x],1);
B.erase(B.find(make_pair(b[x],x)));
}
}
printf("%d\n",ans);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 4
Accepted
time: 1ms
memory: 10044kb
input:
2 2 1 1 1 1 1
output:
2
result:
ok single line: '2'
Test #2:
score: -4
Wrong Answer
time: 2ms
memory: 16076kb
input:
10 200000 100000 34181 300096 24293 22680 402306 193269 438170 254676 188147 73971 216849 477743 461911 135785 467234 278230 287107 223666 124173 135091
output:
1
result:
wrong answer 1st lines differ - expected: '7', found: '1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Runtime Error
Test #100:
score: 0
Runtime Error
input:
500000 500000 10 200184 74991 71203 334998 316800 34483 120570 301054 331108 232072 189788 397143 490296 56807 361700 88818 42376 460305 371750 450351 338384 429789 426045 445029 152316 408919 188124 144966 457495 475025 225370 260510 383159 495247 54319 246245 240728 372033 439599 119720 449020 451...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%