結果
問題 | No.440 2次元チワワ問題 |
ユーザー | latte0119 |
提出日時 | 2016-10-29 00:11:21 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 180 ms / 5,000 ms |
コード長 | 3,380 bytes |
コンパイル時間 | 1,354 ms |
コンパイル使用メモリ | 147,064 KB |
実行使用メモリ | 18,028 KB |
最終ジャッジ日時 | 2023-08-15 21:55:35 |
合計ジャッジ時間 | 3,714 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,744 KB |
testcase_01 | AC | 3 ms
9,812 KB |
testcase_02 | AC | 3 ms
9,760 KB |
testcase_03 | AC | 3 ms
7,652 KB |
testcase_04 | AC | 4 ms
7,356 KB |
testcase_05 | AC | 3 ms
4,376 KB |
testcase_06 | AC | 4 ms
10,136 KB |
testcase_07 | AC | 10 ms
13,344 KB |
testcase_08 | AC | 27 ms
16,200 KB |
testcase_09 | AC | 53 ms
17,028 KB |
testcase_10 | AC | 17 ms
15,696 KB |
testcase_11 | AC | 9 ms
8,420 KB |
testcase_12 | AC | 14 ms
14,816 KB |
testcase_13 | AC | 43 ms
15,464 KB |
testcase_14 | AC | 3 ms
4,380 KB |
testcase_15 | AC | 46 ms
15,600 KB |
testcase_16 | AC | 7 ms
6,052 KB |
testcase_17 | AC | 64 ms
17,612 KB |
testcase_18 | AC | 52 ms
18,028 KB |
testcase_19 | AC | 64 ms
16,976 KB |
testcase_20 | AC | 55 ms
17,716 KB |
testcase_21 | AC | 155 ms
17,720 KB |
testcase_22 | AC | 180 ms
16,912 KB |
testcase_23 | AC | 143 ms
18,028 KB |
testcase_24 | AC | 175 ms
17,400 KB |
testcase_25 | AC | 165 ms
17,744 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define all(v) (v).begin(),(v).end() #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define pb push_back #define fi first #define se second template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} int H,W; char fld[555][555]; int sumC[555][555]; int val[555][555]; int P[555][555];//-> int Q[555][555];//<- int R[555][555];//v int S[555][555];//^ inline int fC(int a,int b,int c,int d){ return sumC[c][d]-sumC[c][b]-sumC[a][d]+sumC[a][b]; } inline int fW(int a,int b,int c,int d){ return (c-a)*(d-b)-fC(a,b,c,d); } void query(){ int y,x,yy,xx; scanf("%lld%lld%lld%lld",&y,&x,&yy,&xx); y--;x--; int ans=val[yy][xx]-val[yy][x]-val[y][xx]+val[y][x]; for(int i=y;i<yy;i++){ int w=fW(i,x,i+1,xx); ans-=fC(i,0,i+1,x)*w*fW(i,xx,i+1,W); ans-=fW(i,0,i+1,x)*w*fC(i,xx,i+1,W); ans-=(P[i][x]-P[i][xx]-fC(i,x,i+1,xx)*fW(i,xx,i+1,W))*fW(i,xx,i+1,W); ans-=(Q[i][xx]-Q[i][x]-fC(i,x,i+1,xx)*fW(i,0,i+1,x))*fW(i,0,i+1,x); ans-=fC(i,0,i+1,x)*w*(w-1)/2; ans-=fC(i,xx,i+1,W)*w*(w-1)/2; } for(int j=x;j<xx;j++){ int w=fW(y,j,yy,j+1); ans-=fC(0,j,y,j+1)*w*fW(yy,j,H,j+1); ans-=fW(0,j,y,j+1)*w*fC(yy,j,H,j+1); ans-=(R[y][j]-R[yy][j]-fC(y,j,yy,j+1)*fW(yy,j,H,j+1))*fW(yy,j,H,j+1); ans-=(S[yy][j]-S[y][j]-fC(y,j,yy,j+1)*fW(0,j,y,j+1))*fW(0,j,y,j+1); ans-=fC(0,j,y,j+1)*w*(w-1)/2; ans-=fC(yy,j,H,j+1)*w*(w-1)/2; } printf("%lld\n",ans); } signed main(){ scanf("%lld%lld",&H,&W); rep(i,H)scanf("%s",fld[i]); for(int i=0;i<H;i++){ int cnt=0; for(int j=W-1;j>=0;j--){ if(fld[i][j]=='w')cnt++; else{ P[i][j]=cnt; } P[i][j]+=P[i][j+1]; } cnt=0; for(int j=0;j<W;j++){ if(fld[i][j]=='w')cnt++; else{ Q[i][j+1]=cnt; } Q[i][j+1]+=Q[i][j]; } } for(int j=0;j<W;j++){ int cnt=0; for(int i=H-1;i>=0;i--){ if(fld[i][j]=='w')cnt++; else{ R[i][j]=cnt; } R[i][j]+=R[i+1][j]; } cnt=0; for(int i=0;i<H;i++){ if(fld[i][j]=='w')cnt++; else{ S[i+1][j]=cnt; } S[i+1][j]+=S[i][j]; } } rep(i,H){ rep(j,W){ sumC[i+1][j+1]=fld[i][j]=='c'; sumC[i+1][j+1]+=sumC[i][j+1]+sumC[i+1][j]-sumC[i][j]; } } rep(i,H){ rep(j,W){ if(fld[i][j]=='w'){ val[i+1][j+1]+=fC(0,j,i,j+1)*fW(i+1,j,H,j+1); val[i+1][j+1]+=fC(i+1,j,H,j+1)*fW(0,j,i,j+1); val[i+1][j+1]+=fC(i,0,i+1,j)*fW(i,j+1,i+1,W); val[i+1][j+1]+=fC(i,j+1,i+1,W)*fW(i,0,i+1,j); } val[i+1][j+1]+=val[i][j+1]+val[i+1][j]-val[i][j]; } } int Q; scanf("%lld",&Q); while(Q--){ query(); } return 0; }