QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#179313#6673. Be Careful 2lszhWA 0ms3816kbC++142.2kb2023-09-14 20:29:332023-09-14 20:29:34

Judging History

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

  • [2023-09-14 20:29:34]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3816kb
  • [2023-09-14 20:29:33]
  • 提交

answer

#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;typedef pair<int,int>pii;const int N=5005;const int inf=0x3f3f3f3f;const int mod=998244353;const int inv4=748683265,inv6=166374059,inv30=432572553;int n,m,k,ans;pii a[N];void addmod(int&x,int y){(x+=y)-=x>=mod?mod:0;}int qmi(int a,int n){int ret=1;while(n){if(n&1)ret=1ll*ret*a%mod;a=1ll*a*a%mod;n>>=1;}return ret;}int calc2(int x){return 1ll*x*(x+1)%mod*(2*x+1)%mod*inv6%mod;}int calc3(int x){return 1ll*x*x%mod*(x+1)%mod*(x+1)%mod*inv4%mod;}int calc4(int x){return 1ll*x*(x+1)%mod*(2*x+1)%mod*(3ll*x*x%mod+3ll*x-1+mod)%mod*inv30%mod;}int calc(int n,int m){if(n<0||m<0)return 0;int k=min(n,m);int ans=(calc4(k)-1ll*calc3(k)*(n+m+2)%mod+mod+1ll*calc2(k)*((1ll*n*m+n+m+1)%mod))%mod;return ans;}int calc(int x,int y,int n,int m){return(1ll*calc(n,m)-calc(x,m)-calc(n,y)-calc(n-x,m)-calc(n,m-y)+calc(x,y)+calc(n-x,y)+calc(x,m-y)+calc(n-x,m-y)+4ll*mod)%mod;}int query(int sx,int sy,int tx,int ty){return(1ll*calc(tx,ty,n,m)-calc(tx-sx,ty,n-sx,m)-calc(tx,ty-sy,n,m-sy)+calc(tx-sx,ty-sy,n-sx,m-sy)+mod*2)%mod;}int main(){scanf("%d%d%d",&n,&m,&k);addmod(ans,calc(n,m));for(int i=1;i<=k;i++)scanf("%d%d",&a[i].fi,&a[i].se);sort(a+1,a+k+1);for(int i=1;i<=k;i++){int up=inf,down=-inf;addmod(ans,mod-query(a[i].fi,a[i].se,a[i].fi,a[i].se));for(int j=i+1;j<=k;j++){if(a[i].se==a[j].se){addmod(ans,query(a[i].fi,a[i].se,a[j].fi,a[j].se));if(up!=inf)addmod(ans,mod-query(a[i].fi,a[i].se,a[j].fi,up));if(down!=-inf)addmod(ans,mod-query(a[i].fi,down,a[j].fi,a[j].se));if(up!=inf&&down!=-inf)addmod(ans,query(a[i].fi,down,a[j].fi,up));break;}if(a[j].se>a[i].se){if(a[j].se<up){addmod(ans,query(a[i].fi,a[i].se,a[j].fi,a[j].se));if(up!=inf)addmod(ans,mod-query(a[i].fi,a[i].se,a[j].fi,up));if(down!=-inf)addmod(ans,mod-query(a[i].fi,down,a[j].fi,a[j].se));if(up!=inf&&down!=-inf)addmod(ans,query(a[i].fi,down,a[j].fi,up));up=a[j].se;}}else{if(j<k&&a[j+1].fi==a[j].fi&&a[j+1].se<=a[i].se)continue;if(a[j].se>down){addmod(ans,query(a[i].fi,a[j].se,a[j].fi,a[i].se));if(up!=inf)addmod(ans,mod-query(a[i].fi,a[j].se,a[j].fi,up));if(down!=-inf)addmod(ans,mod-query(a[i].fi,down,a[j].fi,a[j].se));if(up!=inf&&down!=-inf)addmod(ans,query(a[i].fi,down,a[j].fi,up));down=a[j].se;}}}}cout<<ans;return 0;}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

3 3 1
2 2

output:

21

result:

ok 1 number(s): "21"

Test #2:

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

input:

5 5 2
2 1
2 4

output:

126

result:

ok 1 number(s): "126"

Test #3:

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

input:

6 6 5
4 1
3 2
2 4
1 5
5 3

output:

161

result:

ok 1 number(s): "161"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3548kb

input:

15 38 6
12 6
7 15
2 18
3 19
4 2
14 29

output:

79616

result:

wrong answer 1st numbers differ - expected: '80066', found: '79616'