QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#420021 | #4887. Fast Bridges | do_while_true | TL | 1799ms | 11444kb | C++20 | 3.6kb | 2024-05-24 13:57:17 | 2024-05-24 13:57:18 |
Judging History
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...