QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420021#4887. Fast Bridgesdo_while_trueTL 1799ms11444kbC++203.6kb2024-05-24 13:57:172024-05-24 13:57:18

Judging History

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

  • [2024-05-24 13:57:18]
  • 评测
  • 测评结果:TL
  • 用时:1799ms
  • 内存:11444kb
  • [2024-05-24 13:57:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int inv6=166374059,mod=998244353;
int tot1,tot2,n,m,x[1005],y[1005],ans,e[1005][1005],vis[1005],val[1005];
struct node{int x1,y1,x2,y2;}a[1005],b[1005];vector<int>v[1005];
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
struct DS
{
	set<int>s;int val[1005],ans,len;
	void init(int x)
	{
		for(int i=1;i<=tot2;i++)val[i]=0;
		s.clear();ans=0;len=x;
	}
	void upd(int k,int v)
	{
		if(v==0)return;
		if(!s.size()){s.insert(k);val[k]=v;Add(ans,1ll*(y[tot2]-y[k])*v%mod*len%mod);return;}
		auto it=s.upper_bound(k);
		if(it!=s.begin()&&val[*prev(it)]>=v)return;
		if(it!=s.begin())Add(ans,mod-1ll*val[*prev(it)]*((it==s.end()?y[tot2]:y[*it])-y[k])%mod*len%mod); 
		int flag=0,pos=0;
		for(auto it2=it;it2!=s.end();it2=s.erase(it2))
		{
			if(val[*it2]>v){flag=1;pos=*it2;break;}
			Add(ans,mod-1ll*val[*it2]*(next(it2)==s.end()?y[tot2]-y[*it2]:y[*next(it2)]-y[*it2])%mod*len%mod);
		}
		s.insert(k);val[k]=v;
		if(flag==0)Add(ans,1ll*v*(y[tot2]-y[k])%mod*len%mod);
		else Add(ans,1ll*v*(y[pos]-y[k])%mod*len%mod);
	}
}ds[1005];
void solve(int m)
{
	tot1=0,tot2=0;
	for(int i=1;i<=m;i++)
	{
		x[++tot1]=a[i].x1+1;x[++tot1]=a[i].x2;
		y[++tot2]=a[i].y1+1;y[++tot2]=a[i].y2;
	}
	x[++tot1]=1;x[++tot1]=n+1;y[++tot2]=1;y[++tot2]=n+1;
	sort(x+1,x+tot1+1);sort(y+1,y+tot2+1);
	tot1=unique(x+1,x+tot1+1)-x-1;tot2=unique(y+1,y+tot2+1)-y-1;
	for(int i=1;i<=m;i++)
	{
		a[i].x1=lower_bound(x+1,x+tot1+1,a[i].x1+1)-x;
		a[i].x2=lower_bound(x+1,x+tot1+1,a[i].x2)-x;
		a[i].y1=lower_bound(y+1,y+tot2+1,a[i].y1+1)-y;
		a[i].y2=lower_bound(y+1,y+tot2+1,a[i].y2)-y;
	}
	for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)e[i][j]=-0x3f3f3f3f;
	for(int i=1;i<=m;i++)e[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i==j)continue;
			if(a[i].x2<a[j].x1&&a[i].y2<a[j].y1)e[i][j]=1;
		}
	}
	for(int k=1;k<=m;k++)
	{
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=m;j++)e[i][j]=max(e[i][j],e[i][k]+e[k][j]);
		}
	}
	for(int i=1;i<=tot1;i++)v[i].clear();
	for(int i=1;i<=m;i++)v[a[i].x2].emplace_back(i); 
	for(int i=1;i<tot1;i++)
	{
		for(int j=1;j<tot2;j++)ds[j].init(y[j+1]-y[j]);
		for(int j=1;j<=m;j++)vis[j]=0;
		for(int j=i;j<tot1;j++)
		{
			for(int k=0;k<v[j].size();k++)
			{
				int x=v[j][k];
				if(a[x].x1<=i)continue;
				vis[x]=1;
				for(int p=1;p<=a[x].y2;p++)val[p]=0;
				for(int p=1;p<=m;p++)
				{
					if(!vis[p])continue;
					int w=e[p][x]+1;
					if(w<0)continue;
					int l=a[p].y1-1,r=a[x].y2;
					if(l>r||w==0)continue;
					val[l]=max(val[l],w); 
				}
				for(int p=a[x].y2-1;p>=1;p--)val[p]=max(val[p],val[p+1]);
				for(int p=1;p<a[x].y2;p++)ds[p].upd(a[x].y2,val[p]);
			}
			int val=1ll*(x[j+1]-x[j])*(x[i+1]-x[i])%mod,res=0;
			for(int p=1;p<tot2;p++)Add(res,ds[p].ans);
			Add(ans,1ll*res*val%mod);
		}
	}
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>m>>n;int flag=1;
	for(int i=1;i<=m;i++)cin>>b[i].x1>>b[i].y1>>b[i].x2>>b[i].y2,flag&=(b[i].y1<b[i].y2);
	for(int i=1;i<m;i++)flag&=(b[i].x2<=b[i+1].x1&&b[i].y2<=b[i+1].y1);
	if(flag==1)
	{
		for(int i=1;i<=m;i++)Add(ans,1ll*b[i].x1*b[i].y1%mod*(n-b[i].x2+1)%mod*(n-b[i].y2+1)%mod);
		ans=1ll*ans*2%mod;
	}
	else 
	{
		int cnt=0;
		for(int i=1;i<=m;i++)if(b[i].y1<b[i].y2)a[++cnt]=b[i];
		solve(cnt);cnt=0;
		for(int i=1;i<=m;i++)b[i].y1=n-b[i].y1+1,b[i].y2=n-b[i].y2+1;
		for(int i=1;i<=m;i++)if(b[i].y1<b[i].y2)a[++cnt]=b[i];
		solve(cnt);ans=1ll*ans*2%mod;
	}
	int res=1ll*n*n%mod*(n-1)%mod*n%mod*(n+1)%mod*inv6%mod*4%mod;
	res=(res-ans+mod)%mod;res=1ll*res*((mod+1)/2)%mod;
	cout<<res;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 8844kb

input:

2 2
1 1 2 2
1 2 2 1

output:

6

result:

ok answer is '6'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7632kb

input:

0 1000000000

output:

916520226

result:

ok answer is '916520226'

Test #3:

score: 0
Accepted
time: 1ms
memory: 7724kb

input:

5 5
1 1 3 3
3 3 5 1
3 3 4 5
3 3 5 4
1 5 3 3

output:

946

result:

ok answer is '946'

Test #4:

score: 0
Accepted
time: 3ms
memory: 9560kb

input:

200 5
1 1 4 2
2 5 4 4
2 3 4 2
2 4 3 5
1 4 4 2
2 5 4 2
1 2 4 4
1 2 2 4
1 4 5 1
3 4 5 1
4 2 5 1
2 2 5 4
3 2 5 1
3 1 5 2
4 2 5 3
1 3 5 1
3 4 4 5
2 2 4 3
2 3 5 4
1 4 5 3
2 2 3 1
2 5 3 3
1 1 5 3
4 4 5 5
1 3 4 4
4 3 5 1
2 3 3 4
3 4 4 2
1 4 4 5
2 1 4 4
1 3 5 2
1 1 3 3
1 5 3 1
1 1 3 5
1 4 3 5
4 5 5 4
1 1 4 ...

output:

708

result:

ok answer is '708'

Test #5:

score: 0
Accepted
time: 25ms
memory: 10596kb

input:

500 10
5 6 7 10
1 3 8 10
3 3 4 9
2 10 10 2
9 4 10 10
5 4 7 8
7 1 10 7
3 1 7 10
5 2 8 9
6 3 7 10
3 10 7 9
4 9 5 1
2 5 3 3
7 10 8 2
7 7 9 8
6 6 8 3
5 10 8 8
1 1 5 5
3 3 10 5
5 5 7 6
3 8 4 7
6 7 7 5
7 3 10 9
5 3 9 4
4 6 10 5
1 5 9 10
5 6 9 7
3 10 10 3
1 2 5 7
4 6 5 1
3 1 8 5
5 8 8 9
1 8 4 3
6 4 7 10
7 ...

output:

27373

result:

ok answer is '27373'

Test #6:

score: 0
Accepted
time: 28ms
memory: 9484kb

input:

500 30
3 13 20 29
14 5 16 25
2 29 9 15
23 30 24 9
1 18 24 28
4 16 5 2
3 29 30 25
4 8 24 19
8 26 10 24
20 14 26 25
15 8 25 25
5 13 18 28
3 30 29 10
14 26 25 11
11 19 16 4
9 4 29 30
15 10 16 8
2 29 12 2
11 22 20 28
4 10 28 1
24 17 30 1
8 26 27 9
15 25 30 14
16 20 24 17
9 23 12 13
9 16 25 28
2 15 8 16
...

output:

7717993

result:

ok answer is '7717993'

Test #7:

score: 0
Accepted
time: 42ms
memory: 9748kb

input:

500 100
25 55 55 43
14 22 84 5
57 7 79 15
63 9 86 23
22 3 53 97
2 22 64 65
32 52 66 30
76 37 79 22
46 100 76 22
21 78 78 44
29 41 92 55
43 14 46 3
14 97 42 1
16 7 35 64
15 27 29 3
11 92 92 70
4 13 66 2
3 38 55 82
41 94 83 44
52 90 100 82
6 100 99 70
18 38 24 22
74 17 98 20
17 94 44 82
33 97 48 19
12...

output:

291628571

result:

ok answer is '291628571'

Test #8:

score: 0
Accepted
time: 85ms
memory: 9860kb

input:

500 8
2 4 8 2
3 7 5 4
2 6 8 1
4 8 5 5
6 6 7 5
2 6 5 5
1 6 8 5
6 5 7 3
4 8 5 7
5 7 6 5
1 6 4 5
2 3 4 2
2 8 8 6
3 8 4 3
5 6 7 2
7 8 8 3
1 8 4 7
1 6 6 1
1 8 7 1
1 4 3 3
2 3 3 1
1 4 5 1
1 8 5 4
7 7 8 5
2 7 4 1
3 7 4 3
2 3 5 1
3 7 8 1
4 7 5 5
6 6 8 3
2 7 5 1
2 5 4 3
5 4 8 2
4 5 8 3
2 3 4 1
2 8 3 2
5 6 8 ...

output:

9321

result:

ok answer is '9321'

Test #9:

score: 0
Accepted
time: 443ms
memory: 9628kb

input:

500 1000000000
228604634 522874974 789854111 585676486
340802063 175643637 661594207 749079321
490078806 844144515 583746323 707696611
833939453 901516824 867397264 848066012
553537526 886003963 679012061 187030606
351500555 847099665 751201742 855105070
169763646 729114554 248951243 211939611
17040...

output:

230090667

result:

ok answer is '230090667'

Test #10:

score: 0
Accepted
time: 1646ms
memory: 10024kb

input:

500 1000000000
536804949 618264275 757262973 133194920
206604343 420304040 244005624 331707206
64548973 877773848 685024560 565782395
13572244 271309598 835979107 128627415
128103153 561746493 703898577 9276472
209282309 997406956 216339996 279878227
386095652 999498735 908610032 582414132
232191790...

output:

404991176

result:

ok answer is '404991176'

Test #11:

score: 0
Accepted
time: 1799ms
memory: 10444kb

input:

500 1000000000
435165109 887707979 541968631 834720917
43164344 595179931 731392283 541750474
51147932 885859385 525997101 813310992
581745995 569929983 666239343 349298365
720599913 330436249 751561895 84593980
254142704 924477087 706739688 760929039
282091849 414650019 853811117 121534462
21407507...

output:

174105246

result:

ok answer is '174105246'

Test #12:

score: 0
Accepted
time: 1789ms
memory: 11444kb

input:

500 1000000000
334968963 60182667 683993047 330063742
372714145 727060351 391638535 972082352
15288009 443033033 549932294 626507494
551292358 201286324 844192128 989162325
138957062 834473180 233314539 840742618
774917762 293038146 784290713 868100668
88362426 108423246 90763875 635080794
197409326...

output:

819654628

result:

ok answer is '819654628'

Test #13:

score: 0
Accepted
time: 1756ms
memory: 10408kb

input:

500 1000000000
407797655 600906761 451028876 557753318
739109786 505834673 914488662 267694229
21613693 815099602 741520301 86754775
749426136 864500481 989644055 760004108
97929570 281277866 645537954 194083134
386298407 900097354 590149576 876589970
225981751 604462892 313700311 201620926
13512935...

output:

704804476

result:

ok answer is '704804476'

Test #14:

score: 0
Accepted
time: 447ms
memory: 9600kb

input:

500 1000000000
136588729 322381152 198423052 586895024
146201252 78771798 320963978 33171878
103014217 582579333 112482565 472327049
363500012 171569343 779799989 210605961
916348434 897403875 958218658 848653603
81959275 288412262 293263271 877464982
155884974 409342051 490632310 353856648
42868173...

output:

701057894

result:

ok answer is '701057894'

Test #15:

score: 0
Accepted
time: 465ms
memory: 9600kb

input:

500 1000000000
70732466 818210159 101241592 180120566
551559764 430141447 558477026 919623562
842854549 898003264 988655980 690377539
365038538 842566580 988616538 612555368
119137999 522482797 776356145 341894154
134943863 753491473 621956497 857574689
860979233 313689040 912231580 819779431
253383...

output:

849305849

result:

ok answer is '849305849'

Test #16:

score: 0
Accepted
time: 457ms
memory: 9644kb

input:

500 1000000000
76067493 226360208 588463712 997370258
247139391 228988779 876938260 628658287
173490201 249999131 402004522 332729284
73514885 82656638 357464837 702514607
288650085 526722777 582817141 741491871
859774917 73498480 878952996 868608989
248586909 115745356 485233299 599896403
302539166...

output:

980753674

result:

ok answer is '980753674'

Test #17:

score: -100
Time Limit Exceeded

input:

500 919069957
742507159 740217847 742778031 741238898
320301045 312370945 321929532 313537690
344928356 347275650 349920032 348402734
128430402 156747983 128702472 159673979
89940237 122339622 90602165 123930504
638094551 604903042 638437986 606101004
118489244 152414022 121260981 154139858
41785067...

output:


result: