QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#164469 | #5378. 匹配问题 | Benzenesir | 4 | 190ms | 19308kb | C++14 | 2.8kb | 2023-09-04 23:47:42 | 2023-09-04 23:47:42 |
Judging History
answer
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <stack>
#include <tuple>
#include <bitset>
#include <time.h>
#include <random>
#define ll long long
#define ull unsigned long long
#define ld long double
#define fp(a, b, c) for (int a = b; a <= c; a++)
#define fd(a, b, c) for (int a = b; a >= c; a--)
#define pii pair<int, int>
#define inf 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define eb emplace_back
#define pb pop_back
#define y1 y114
#define y0 y514
#define x1 x114
#define x0 x514
#define mpr make_pair
#define met(x, t) memset(x, t, sizeof(x))
#define fir first
#define sec second
using namespace std;
inline int rd() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
const int N = 5e5 + 10;
int n, lenb, lena;
int a[N], b[N], L[N], R1[N], R2[N],vis[N];
struct segment{
int data[N<<4],tag[N<<4];
void pushdown(int now,int l,int mid,int r){
if(tag[now]){
tag[now<<1]+=tag[now],
tag[now<<1|1]+=tag[now];
data[now<<1]+=tag[now]*(mid-l+1),
data[now<<1|1]+=tag[now]*(r-mid),
tag[now]=0;
}
}
void pushup(int now){data[now]=min(data[now<<1],data[now<<1|1]);}
void modify(int now,int l,int r,int ql,int qr,int x){
if(ql>qr) return;
if(ql<=l&&r<=qr) return data[now]+=(r-l+1)*x,tag[now]+=x,void();
int mid(l+r>>1);
pushdown(now,l,mid,r);
if(ql<=mid) modify(now<<1,l,mid,ql,qr,x);
if(qr>mid) modify(now<<1|1,mid+1,r,ql,qr,x);
pushup(now);
}
int query(int now,int l,int r,int ql,int qr){
if(ql>qr) return inf;
if(ql<=l&&r<=qr) return data[now];
int mid(l+r>>1);
pushdown(now,l,mid,r);
if(qr<=mid) return query(now<<1,l,mid,ql,qr);
else if(ql>mid) return query(now<<1|1,mid+1,r,ql,qr);
else return min(query(now<<1,l,mid,ql,qr),query(now<<1|1,mid+1,r,ql,qr));
}
}seg;
void fl() {
freopen("match.in", "r", stdin);
freopen("match.out", "w", stdout);
}
signed main() {
n = rd(), lena = rd(), lenb = rd();
fp(i, 1, n) a[i] = rd();
fp(i, 1, n) b[i] = rd();
sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);
int j=n;
fd(i,n,1){
while(j&&a[j]+lena>=b[i]) j--;
seg.modify(1,1,n,i,i,i-j-1);
}
int last=n,ans=0,p=n;
fd(i,n,1){
while(p>=1&&b[p]>a[i]+lenb) p--;
while(vis[last]) last--;
if(p&&seg.query(1,1,n,p+1,last)>0&&b[p]>=a[i]){
seg.modify(1,1,n,p,p,inf);
seg.modify(1,1,n,p+1,last,-1);
vis[p]=1,++ans,p--;
}else vis[last]=1;
}
cout << ans << endl;
return 0;
}
// g++ D.cpp -o D.exe -std=c++14
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 2ms
memory: 7552kb
input:
2 2 1 1 1 1 1
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7612kb
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:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7536kb
input:
10 200000 50000 298370 136488 436143 52173 206095 140981 321188 407844 342157 193338 138374 383207 156748 442404 386749 492604 354156 229996 447123 418264
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5372kb
input:
10 50000 30000 306273 53088 405351 218373 335275 277816 451436 105244 418031 83336 489843 323727 219514 102964 141689 337190 131790 312365 431836 413688
output:
5
result:
ok single line: '5'
Test #5:
score: 0
Accepted
time: 2ms
memory: 7536kb
input:
10 80000 60000 224299 63826 419731 459681 408367 139676 239118 115180 368327 179613 289195 106688 418781 143169 441337 255686 228353 373168 489321 173199
output:
10
result:
ok single line: '10'
Test #6:
score: 0
Accepted
time: 2ms
memory: 7664kb
input:
10 150000 80000 218617 21495 443909 77126 349241 169574 387539 106419 251533 138042 427196 237082 192262 56014 357102 109789 495939 197573 273744 498979
output:
7
result:
ok single line: '7'
Test #7:
score: 0
Accepted
time: 2ms
memory: 7620kb
input:
10 5 1 1 28 22 4 16 13 7 10 19 25 6 9 27 12 30 24 18 15 3 21
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 2ms
memory: 7612kb
input:
10 2 1 19 13 16 22 28 25 7 1 4 10 6 21 30 9 15 12 27 18 3 24
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 7504kb
input:
9 5 1 9 1 12 2 16 5 8 15 19 18 20 4 7 14 6 21 13 11
output:
3
result:
ok single line: '3'
Test #10:
score: 0
Accepted
time: 0ms
memory: 7532kb
input:
10 500000 1 13 1 16 4 22 7 10 28 25 19 9 3 30 18 24 15 6 20 27 12
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 0ms
memory: 7672kb
input:
3 2 1 1 2 3 3 4 5
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 2ms
memory: 7512kb
input:
10 500000 499999 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282 375282
output:
10
result:
ok single line: '10'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #13:
score: 0
Wrong Answer
time: 2ms
memory: 7632kb
input:
100 200000 50000 216198 375994 364079 318600 289827 26059 302540 179976 362307 239456 310052 149745 283732 189278 465297 19986 492322 62889 399607 354136 103590 327594 335929 428453 474630 362205 113883 219196 488463 150086 144585 8342 98764 454065 282581 397786 274728 271563 326538 246226 384730 25...
output:
44
result:
wrong answer 1st lines differ - expected: '63', found: '44'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #100:
score: 0
Wrong Answer
time: 190ms
memory: 19308kb
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:
861
result:
wrong answer 1st lines differ - expected: '312193', found: '861'
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%