QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#65472 | #833. Cells Blocking | xiaoyaowudi | AC ✓ | 167ms | 133520kb | C++14 | 2.7kb | 2022-12-01 10:59:15 | 2022-12-01 10:59:17 |
Judging History
answer
#include <algorithm>
#include <iostream>
constexpr int N(3010);
int main()
{
static char s[N][N];
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n,m,c(0);std::cin>>n>>m;
for(int i(1);i<=n;++i)
{
std::cin>>s[i]+1;
for(int j(1);j<=m;++j) c+=(s[i][j]=='.');
}
static bool clu[N][N],crd[N][N];
if(s[1][1]=='.') clu[1][1]=1;if(s[n][m]=='.') crd[n][m]=true;
for(int i(1);i<=n;++i) for(int j(1);j<=m;++j) if(i!=1 || j!=1) {if(s[i][j]=='*') clu[i][j]=false;else clu[i][j]=clu[i-1][j]|clu[i][j-1];}
for(int i(n);i;--i) for(int j(m);j;--j) if(i!=n || j!=m) {if(s[i][j]=='*') crd[i][j]=false;else crd[i][j]=crd[i+1][j]|crd[i][j+1];}
if(!clu[n][m])
{
std::cout<<1ll*c*(c-1)/2<<std::endl;
return 0;
}
static bool cap[N][N];
for(int i(1);i<=n;++i) for(int j(1);j<=m;++j) cap[i][j]=clu[i][j]&crd[i][j];
static int idx1[N][N],idx2[N][N];idx1[1][1]=idx2[1][1]=1;
static std::pair<int,int> p1[N<<1],p2[N<<1];p1[1]=p2[1]={1,1};
for(int i(1),x(1),y(1);i<=n+m-2;++i)
{
if(cap[x+1][y]) ++x;
else ++y;
idx1[x][y]=i+1;
p1[i+1]={x,y};
}
for(int i(1),x(1),y(1);i<=n+m-2;++i)
{
if(cap[x][y+1]) ++y;
else ++x;
idx2[x][y]=i+1;
p2[i+1]={x,y};
}
int cnt(0);
for(int i(1);i<=n;++i) for(int j(1);j<=m;++j) cnt+=(idx1[i][j] && idx2[i][j]);
int ans(cnt*(cnt-1)/2+cnt*(c-cnt));
static int g[N][N],h[N][N];
for(int i(1);i<=n;++i) for(int j(1);j<=m;++j) if(cap[i][j])
{
if(idx2[i][j]) g[i][j]=idx2[i][j];
else
{
g[i][j]=1e9;
if(cap[i-1][j]) g[i][j]=std::min(g[i][j],g[i-1][j]);
if(cap[i][j-1]) g[i][j]=std::min(g[i][j],g[i][j-1]);
}
}
for(int i(n);i;--i) for(int j(m);j;--j) if(cap[i][j])
{
if(idx2[i][j]) h[i][j]=idx2[i][j];
else
{
h[i][j]=0;
if(cap[i+1][j]) h[i][j]=std::max(h[i][j],h[i+1][j]);
if(cap[i][j+1]) h[i][j]=std::max(h[i][j],h[i][j+1]);
}
}
static int pre[N<<1],suf[N<<1];
for(int i(1);i<=n+m-1;++i)
{
auto [x,y]=p2[i];
if(idx1[x][y]) pre[i]=0;
else
{
int r(1e9);
if(cap[x-1][y]) r=std::min(r,g[x-1][y]);
if(cap[x][y-1]) r=std::min(r,g[x][y-1]);
pre[i]=pre[r]+1;
}
}
for(int i(n+m-1);i;--i)
{
auto [x,y]=p2[i];
if(idx1[x][y]) suf[i]=0;
else
{
int r(0);
if(cap[x+1][y]) r=std::max(r,h[x+1][y]);
if(cap[x][y+1]) r=std::max(r,h[x][y+1]);
suf[i]=suf[r]+1;
}
}
for(int i(1),j(0);i<=n+m-1;++i)
{
auto [x,y]=p1[i];
if(idx2[x][y]){j=i;continue;}
int r(1e9),l(0);
for(int t(y+1);t<=m;++t) if(cap[x-1][t])
{
r=std::min(r,g[x-1][t]),l=std::max(l,h[x-1][t]);
if(idx2[x-1][t]) break;
}
// std::cerr<<x<<" "<<y<<" "<<l<<" "<<r<<" "<<pre[r]<<" "<<suf[l]<<" "<<pre[r]+suf[l]-(l==r)<<std::endl;
ans+=pre[r]+suf[l]-(l==r);
}
std::cout<<ans<<std::endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 9736kb
input:
3 3 ... ... ...
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 0
Accepted
time: 3ms
memory: 9640kb
input:
3 3 .** .*. ...
output:
15
result:
ok 1 number(s): "15"
Test #3:
score: 0
Accepted
time: 2ms
memory: 9632kb
input:
3 4 **** .... ****
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7452kb
input:
5 5 *.... .*.*. ***** *.*** ..*..
output:
66
result:
ok 1 number(s): "66"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7612kb
input:
10 10 ...***.*.. **...*.*** ...***.*.. .**...*.*. .*****..*. ..*.****.* .**...**** ..*..*.*.* *.*.**.... ....**...*
output:
1378
result:
ok 1 number(s): "1378"
Test #6:
score: 0
Accepted
time: 114ms
memory: 133392kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17999999
result:
ok 1 number(s): "17999999"
Test #7:
score: 0
Accepted
time: 135ms
memory: 133400kb
input:
3000 3000 ...................................................................................................................*......................................................................................................................................................................*..........
output:
17981671
result:
ok 1 number(s): "17981671"
Test #8:
score: 0
Accepted
time: 112ms
memory: 133424kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17963615
result:
ok 1 number(s): "17963615"
Test #9:
score: 0
Accepted
time: 151ms
memory: 133324kb
input:
3000 3000 .........................................................................................................*...........................................................................................................................................................................................
output:
17945165
result:
ok 1 number(s): "17945165"
Test #10:
score: 0
Accepted
time: 141ms
memory: 133320kb
input:
3000 3000 ......................................................................................................................................*........................................................................................................................................*.....................
output:
17928211
result:
ok 1 number(s): "17928211"
Test #11:
score: 0
Accepted
time: 146ms
memory: 133308kb
input:
3000 3000 ...........................................*.........................................................................................................................................................................................................................................................
output:
17911522
result:
ok 1 number(s): "17911522"
Test #12:
score: 0
Accepted
time: 132ms
memory: 133116kb
input:
3000 3000 ..............................*................................................................................................................*.....................................................................................................................................................
output:
17892283
result:
ok 1 number(s): "17892283"
Test #13:
score: 0
Accepted
time: 113ms
memory: 133392kb
input:
3000 3000 ................................................................*....*................................................................................................................................................................................*..............................................
output:
17873837
result:
ok 1 number(s): "17873837"
Test #14:
score: 0
Accepted
time: 144ms
memory: 133148kb
input:
3000 3000 ............................................................................................*.............................................................................*.....................................................................................................*....................
output:
17856701
result:
ok 1 number(s): "17856701"
Test #15:
score: 0
Accepted
time: 147ms
memory: 133260kb
input:
3000 3000 ......................................*..........................................................................................................................................................*...................................................................................................
output:
17837857
result:
ok 1 number(s): "17837857"
Test #16:
score: 0
Accepted
time: 129ms
memory: 133096kb
input:
3000 3000 .................................................................................................................................................................................................................................*...................................................................
output:
17819731
result:
ok 1 number(s): "17819731"
Test #17:
score: 0
Accepted
time: 151ms
memory: 129740kb
input:
3000 3000 ......**.....*.......*.*..........*..*...............**.............*.......*......*........*...*.....*.*.................*......*....*.........*....................*.................*.......................*.......*..*.*.......*.......................*..........*..*......................*...
output:
16202000
result:
ok 1 number(s): "16202000"
Test #18:
score: 0
Accepted
time: 156ms
memory: 121084kb
input:
3000 3000 ..................*....*....*...*.*.............*.............*....*.*..*...*...*...*....*.................*...*.*.***...*....*......*.......**...*.......*.*...**...*...*...**.........*..........*.....*.*....*..*.......*.........*..*.....*...............**.......*.....*.*..*.*.*........*.....
output:
21600132
result:
ok 1 number(s): "21600132"
Test #19:
score: 0
Accepted
time: 88ms
memory: 29928kb
input:
3000 3000 ..*.**...*...............*........*.*..*.*.....*........*.*..........***..*..*..*..*.*....*...*.*.....***.*...*........*..*.****..*.*....**.......*......*....*..*......*......*..*..*.*..*....*..**.*.......**.*...*....**.....**..*......*...*....*..*.**.*..***...*.....*....***.*........*.......
output:
19862779430431
result:
ok 1 number(s): "19862779430431"
Test #20:
score: 0
Accepted
time: 98ms
memory: 29920kb
input:
3000 3000 .**.**..***....*.*....*..*...*.**.**.**.......*...*........*.**.*...*...**..*...*.*.**.*.*.*.*..*...*.....*.*.**.*.*....*.**.....*..**.**.*....**.**.**..*..**...*...***.**.*.*......**.**.*...****.....***.*..*.**.*......*..**.**.**.....**...*.*..***.******...**....****..***..**.*........*.....
output:
14601805246666
result:
ok 1 number(s): "14601805246666"
Test #21:
score: 0
Accepted
time: 4ms
memory: 5544kb
input:
1 1 *
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 4ms
memory: 9512kb
input:
1 1 .
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 3ms
memory: 9720kb
input:
2 2 .. ..
output:
6
result:
ok 1 number(s): "6"
Test #24:
score: 0
Accepted
time: 109ms
memory: 29776kb
input:
3000 3000 .***..**..*.*.*..*...**.*.**...***.....*..***.***.***.*..***.*......*.**.***.***.*...**.*.*..***.*..*.**..***.....*.*...***.*.***.*...*.*.....***.*..**...*.*..*.******.*.*...**.*..**.**.**.*.**..***.**.***..*......**.***.**.*....*..*.....*...*..*.*..*..*.*...**.**...*..**..***.**..*....*.....
output:
10151159625145
result:
ok 1 number(s): "10151159625145"
Test #25:
score: 0
Accepted
time: 27ms
memory: 29828kb
input:
3000 3000 *******************************************************************************************************************************************************************************************************************************************************.******************************************...
output:
39716328
result:
ok 1 number(s): "39716328"
Test #26:
score: 0
Accepted
time: 129ms
memory: 133336kb
input:
3000 3000 ..*..................................................................................................................................................................................................................................................................................................
output:
35988321
result:
ok 1 number(s): "35988321"
Test #27:
score: 0
Accepted
time: 129ms
memory: 133396kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
35981866
result:
ok 1 number(s): "35981866"
Test #28:
score: 0
Accepted
time: 124ms
memory: 133356kb
input:
3000 3000 ...**................................................................................................................................................................................................................................................................................................
output:
17988153
result:
ok 1 number(s): "17988153"
Test #29:
score: 0
Accepted
time: 127ms
memory: 133468kb
input:
3000 3000 ...*.*...............................................................................................................................................................................................................................................................................................
output:
35969654
result:
ok 1 number(s): "35969654"
Test #30:
score: 0
Accepted
time: 114ms
memory: 133316kb
input:
3000 3000 ..*..................................................................................................................................................................................................................................................................................................
output:
17982216
result:
ok 1 number(s): "17982216"
Test #31:
score: 0
Accepted
time: 140ms
memory: 133324kb
input:
3000 3000 ....**.*.............................................................................................................................................................................................................................................................................................
output:
71916090
result:
ok 1 number(s): "71916090"
Test #32:
score: 0
Accepted
time: 124ms
memory: 133408kb
input:
3000 3000 ....****.............................................................................................................................................................................................................................................................................................
output:
71903186
result:
ok 1 number(s): "71903186"
Test #33:
score: 0
Accepted
time: 135ms
memory: 133512kb
input:
3000 3000 .........*...........................................................................................................................................................................................................................................................................................
output:
17973051
result:
ok 1 number(s): "17973051"
Test #34:
score: 0
Accepted
time: 146ms
memory: 133344kb
input:
3000 3000 .*.......*.............................................................................................................*................................................................................*............................................................................................
output:
35630636
result:
ok 1 number(s): "35630636"
Test #35:
score: 0
Accepted
time: 140ms
memory: 133220kb
input:
3000 3000 .**...........................*..........................................................................................................................................*...........................................................................................................................
output:
44529907
result:
ok 1 number(s): "44529907"
Test #36:
score: 0
Accepted
time: 125ms
memory: 133368kb
input:
3000 3000 ....*................................................................................................................................................................................................................................................................................................
output:
53426863
result:
ok 1 number(s): "53426863"
Test #37:
score: 0
Accepted
time: 126ms
memory: 133144kb
input:
3000 3000 ..*.*........................................................................*............................*...............*.............................................................................................................................................*........*...................
output:
53419301
result:
ok 1 number(s): "53419301"
Test #38:
score: 0
Accepted
time: 116ms
memory: 133328kb
input:
3000 3000 ......*.........*...................................................................................*.....................................................................................................................*................................................*.........................
output:
26705269
result:
ok 1 number(s): "26705269"
Test #39:
score: 0
Accepted
time: 124ms
memory: 133104kb
input:
3000 3000 ....*.**....*................*............................*..........*...............................................................................................................................................................................................................................
output:
17799069
result:
ok 1 number(s): "17799069"
Test #40:
score: 0
Accepted
time: 129ms
memory: 133248kb
input:
3000 3000 ...***.......................................*...........*.....................*........*...........................................................................................................................................................*................................................
output:
53393629
result:
ok 1 number(s): "53393629"
Test #41:
score: 0
Accepted
time: 167ms
memory: 133472kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
98852811
result:
ok 1 number(s): "98852811"
Test #42:
score: 0
Accepted
time: 2ms
memory: 9628kb
input:
1 3000 ........................................................................................................................................................................................................................................................................................................
output:
4498500
result:
ok 1 number(s): "4498500"
Test #43:
score: 0
Accepted
time: 143ms
memory: 133276kb
input:
3000 3000 .*.....*...........................................................................................................*...................................*........................................................................................*............*.......................................
output:
88979547
result:
ok 1 number(s): "88979547"
Test #44:
score: 0
Accepted
time: 126ms
memory: 133520kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
35964327
result:
ok 1 number(s): "35964327"