QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#179045#5378. 匹配问题Lynkcat#4 15ms173576kbC++203.1kb2023-09-14 17:09:192024-07-04 02:00:17

Judging History

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

  • [2024-07-04 02:00:17]
  • 评测
  • 测评结果:4
  • 用时:15ms
  • 内存:173576kb
  • [2023-09-14 17:09:19]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e9
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
#define N 2000005
#define M 2000005
using namespace std;
int n,la,lb;
int a[N],b[N],dp[N],_n;
struct edge
{
	int fm,to,val,cost,nxt;
	edge(int o=0,int a=0,int b=0,int c=0,int d=0)
	{
		fm=o,to=a,val=b,cost=c,nxt=d;
	}
}E[M<<1];
int cnt=1;
int hd[N],dis[N],cur[N],lst[N];
int S,T,ans;
int MC,MF;
int flw[N],ins[N];
void add(int x,int y,int w,int cost)
{
	E[++cnt].to=y;
	E[cnt].fm=x;
	E[cnt].val=w;
	E[cnt].nxt=hd[x];
	E[cnt].cost=cost;
	hd[x]=cnt;
	
	E[++cnt].to=x;
	E[cnt].fm=y;
	E[cnt].val=0;
	E[cnt].nxt=hd[y];
	E[cnt].cost=-cost;
	hd[y]=cnt;
}
bool spfa()
{
	queue<int>q;
	for (int i=1;i<=_n;i++) dis[i]=inf,ins[i]=0,flw[i]=0;
	dis[S]=0;
	q.push(S);
	ins[S]=1;
	flw[S]=inf;
	while (!q.empty())
	{
		int u=q.front();q.pop();
		ins[u]=0;
		for (int i=hd[u];i;i=E[i].nxt)
			if (E[i].val&&dis[E[i].to]>dis[u]+E[i].cost)
			{
				dis[E[i].to]=dis[u]+E[i].cost;
				flw[E[i].to]=min(flw[u],E[i].val);
				lst[E[i].to]=i;
				if (!ins[E[i].to]) ins[E[i].to]=1,q.push(E[i].to);
			}
	}
	if (dis[T]==inf) return 0;
	MF+=flw[T];
	MC+=dis[T]*flw[T];
	int nw=T;
	while (nw!=S)
	{
		E[lst[nw]].val-=flw[T];
		E[lst[nw]^1].val+=flw[T];
		nw=E[lst[nw]].fm;
	}
	return 1;
}	
const int B=100;
void Add(int x,int l,int r,int y)
{
    if (l>r) return;
    // cout<<x<<" "<<l<<" "<<r<<" "<<y<<endl;
    if (r-l+1<=B)
    {
        for (int i=l;i<=r;i++) add(x,i+n,1,-y);
        return;
    }
    add(x,l+2*n,1,-y);
    add(x,r+3*n,1,-y);
    r-=r%B;
    for (int i=l+(B-i%B)%B;i<=r;)
    {
        add(x,i+2*n,1,-y);
        i+=B;
    }
}
void BellaKira()
{
    cin>>n>>la>>lb;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1;i<=n;i++)
        cin>>b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    _n=4*n+2;
    S=4*n+1,T=4*n+2;
    for (int i=1;i<=n;i++)
        add(S,i,1,0),add(i+n,T,1,0);
    for (int i=1;i<=n;i++)
    {
        add(i+2*n,i+n,1,0);
        // cout<<i+2*n<<" "<<i+n<<endl;
        if (i<n&&i%B!=0)
            add(i+2*n,i+1+2*n,inf,0);
    }
    for (int i=1;i<=n;i++)
    {
        add(i+3*n,i+n,1,0);
        // cout<<i+3*n<<" "<<i+n<<endl;
        if (i>1&&i%B!=1)
            add(i+3*n,i-1+3*n,inf,0);
    }
    for (int i=1;i<=n;i++)
    {
        int l=n+1,mid=n+1,r=n+1;
        for (int j=n;j>=1;j--)
        {
            if (b[j]>=a[i])
            {
                l=j;
            }
            if (b[j]>a[i]+lb)
            {
                mid=j;
            } 
            if (b[j]>a[i]+la) r=j;
        }
        // cout<<i<<" "<<l<<" "<<mid<<" "<<r<<endl;
        Add(i,l,mid-1,1);
        Add(i,mid,r-1,0);
    }
    while (spfa());
    cout<<-MC<<'\n';
}
signed main()
{
    IOS;
    cin.tie(0);
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 7ms
memory: 171504kb

input:

2 2 1
1 1
1 1

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 7ms
memory: 171764kb

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: 11ms
memory: 171808kb

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: 171572kb

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: 3ms
memory: 171608kb

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: 0ms
memory: 173576kb

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: 3ms
memory: 171512kb

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: 8ms
memory: 171544kb

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: 8ms
memory: 171764kb

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: 8ms
memory: 171736kb

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: 7ms
memory: 171812kb

input:

3 2 1
1 2 3
3 4 5

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 0ms
memory: 173564kb

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
Runtime Error

Dependency #1:

100%
Accepted

Test #13:

score: 14
Accepted
time: 15ms
memory: 171816kb

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:

63

result:

ok single line: '63'

Test #14:

score: -14
Runtime Error

input:

100 200000 10000
480821 383273 197373 419379 37439 203333 299170 472531 243830 178320 365484 188981 414062 72193 411592 424204 340704 77915 241035 418858 18916 22153 349730 52029 216408 254012 239845 340707 326325 217780 49620 457023 424881 447611 180529 299451 97390 388124 62096 217848 229883 36748...

output:


result:


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:

100%
Accepted

Dependency #2:

0%