QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#179313 | #6673. Be Careful 2 | lszh | WA | 0ms | 3816kb | C++14 | 2.2kb | 2023-09-14 20:29:33 | 2023-09-14 20:29:34 |
Judging History
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'