QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164069#5378. 匹配问题DaiRuiChen0070 0ms0kbC++141.8kb2023-09-04 19:25:142023-09-04 19:25:15

Judging History

你现在查看的是最新测评结果

  • [2023-09-04 19:25:15]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-09-04 19:25:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5,W=1e6;
class SegmentTree {
	private:
		struct Node {
			int add,min;
		}	tr[MAXN<<3];
		inline int L(int p) { return p<<1; }
		inline int R(int p) { return p<<1|1; }
		inline void addtag(int p,int k) { tr[p].add+=k,tr[p].min+=k; }
		inline void pushup(int p) {
			tr[p].min=std::min(tr[L(p)].min,tr[R(p)].min);
		}
		inline void pushdown(int p) {
			addtag(L(p),tr[p].add),addtag(R(p),tr[p].add),tr[p].add=0;
		}
	public:
		inline void Modify(int ul,int ur,int k,int l=1,int r=W,int p=1) {
			if(ul<=l&&r<=ur) return addtag(p,k);
			int mid=(l+r)>>1;
			pushdown(p);
			if(ul<=mid) Modify(ul,ur,k,l,mid,L(p)); 
			if(mid<ur) Modify(ul,ur,k,mid+1,r,R(p));
			pushup(p);
		}
		inline int Query(int ul,int ur,int l=1,int r=W,int p=1) {
			if(ul<=l&&r<=ur) return tr[p].min;
			int mid=(l+r)>>1;
			pushdown(p);
			if(ur<=mid) return Query(ul,ur,l,mid,L(p));
			if(mid<ul) return Query(ul,ur,mid+1,r,R(p));
			return std::min(Query(ul,ur,l,mid,L(p)),Query(ul,ur,mid+1,r,R(p)));
		}
}	TR;
int a[MAXN],b[MAXN];
inline void add(int x,int v) { TR.Modify(x,W,v); }
signed main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int n,ans=0,x,y;
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]); sort(a+1,a+n+1);
	for(int i=1;i<=n;++i) scanf("%d",&b[i]); sort(b+1,b+n+1);
	deque <int> B{b[n]}; add(b[n],1);
	for(int i=n,j=n;i;--i) {
		while(j>=1&&(B.empty()||B.front()>a[i]+y)) {
			add(a[--j]+x,-1),B.push_front(b[j]),add(b[j],1);
		}
		if(j>=1&&B.front()>=a[i]) {
			add(B.front(),-1),add(a[i]+x,1);
			if(TR.Query(1,W)>=0) ++ans,B.pop_front();
			else add(B.front(),1),add(B.back(),-1),B.pop_back();
		}
		else add(B.back(),-1),B.pop_back(),add(a[i]+x,1);
	}
	printf("%d\n",ans);
	return 0;
}

详细

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

2 2 1
1 1
1 1

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Dangerous Syscalls

Test #100:

score: 0
Dangerous Syscalls

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%