QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#339605#5378. 匹配问题Dualqwq0 345ms49156kbC++172.4kb2024-02-27 16:41:042024-02-27 16:41:06

Judging History

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

  • [2024-02-27 16:41:06]
  • 评测
  • 测评结果:0
  • 用时:345ms
  • 内存:49156kb
  • [2024-02-27 16:41:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n,la,lb,m = 5e5;
int a[N],b[N];
int val[N];
int sum[N],Mn[N];
vector<pair<int,int> > Chg[N];
struct SGT {
	static const int Sz = N << 2;
	int Mn[Sz],tag[Sz];
	inline void pushup(int k) { Mn[k] = min(Mn[k << 1],Mn[k << 1 | 1]);}
	inline void Add(int k,int v) { Mn[k] += v;tag[k] += v;}
	inline void pushdown(int k) { if(tag[k]) Add(k << 1,tag[k]),Add(k << 1 | 1,tag[k]),tag[k] = 0;}
	void modify(int k,int l,int r,int x,int y,int v) {
		if(x <= l && r <= y) return Add(k,v);
		int mid = l + r >> 1;
		pushdown(k);
		if(x <= mid) modify(k << 1,l,mid,x,y,v);
		if(mid < y) modify(k << 1 | 1,mid + 1,r,x,y,v);
		pushup(k);
	}
	void Change(int k,int l,int r,int pos,int v) {
		if(l == r) { Mn[k] = min(Mn[k],v);return;}
		int mid = l + r >> 1;
		pushdown(k);
		if(pos <= mid) Change(k << 1,l,mid,pos,v);
		else Change(k << 1 | 1,mid + 1,r,pos,v);
		pushup(k);
	}
	int Query(int k,int l,int r,int x,int y) {
		if(x <= l && r <= y) return Mn[k];
		int mid = l + r >> 1;
		pushdown(k);
		if(y <= mid) return Query(k << 1,l,mid,x,y);
		else if(x > mid) return Query(k << 1 | 1,mid + 1,r,x,y);
		else return min(Query(k << 1,l,mid,x,y),Query(k << 1 | 1,mid + 1,r,x,y));
	}
	void build(int k,int l,int r) {
		tag[k] = 0;
		if(l == r) { Mn[k] = 1e9;return;}
		int mid = l + r >> 1;
		build(k << 1,l,mid);build(k << 1 | 1,mid + 1,r);
		pushup(k);
	}
} T;
void updval(int r) {
	if(r < la) return;
	int p1 = upper_bound(a + 1,a + n + 1,r - la) - (a + 1);
	int p2 = upper_bound(a + 1,a + n + 1,r - lb) - (a + 1);
	Chg[p1 + 1].emplace_back(p2,sum[r] - (p1 + 1) + Mn[p1]);
}
int main() {
	cin >> n >> la >> lb;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= n;i++) cin >> b[i],sum[b[i]]++;
	sort(a + 1,a + n + 1);sort(b + 1,b + n + 1);
	for(int i = 1;i <= m;i++)
		sum[i] += sum[i - 1];
	Mn[0] = 1e9;
	for(int i = 1;i <= n;i++)
		Mn[i] = min(Mn[i - 1],i - sum[a[i] - 1]);
	for(int i = 1;i <= n;i++) updval(a[i] + la),updval(a[i] + lb);
	T.build(1,1,n);
	queue<int> Q;int ans = 0;
	for(int i = 1,j = 1;i <= n;i++) {
		while(j <= n && b[j] <= a[i] + lb) Q.push(b[j++]);
		while(Q.size() && Q.front() < a[i]) Q.pop();
		for(auto [r,v] : Chg[i]) T.Change(1,1,n,r,v);
		if(T.Query(1,1,n,i,n) > 0 && Q.size()) {
			T.modify(1,1,n,i,n,-1);
			Q.pop();++ans;
		}
	}
	cout << ans << endl;
	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 4
Accepted
time: 6ms
memory: 26372kb

input:

2 2 1
1 1
1 1

output:

2

result:

ok single line: '2'

Test #2:

score: -4
Wrong Answer
time: 0ms
memory: 24160kb

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:

5

result:

wrong answer 1st lines differ - expected: '7', found: '5'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #100:

score: 0
Wrong Answer
time: 345ms
memory: 49156kb

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:

0

result:

wrong answer 1st lines differ - expected: '312193', found: '0'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%