QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#327651 | #833. Cells Blocking | ExplodingKonjac | AC ✓ | 137ms | 118476kb | C++20 | 5.9kb | 2024-02-15 11:44:24 | 2024-02-15 11:44:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define OPENIOBUF
namespace FastIO
{
class FastIOBase
{
protected:
#ifdef OPENIOBUF
static const int BUFSIZE=1<<16;
char buf[BUFSIZE+1];
int buf_p=0;
#endif
FILE *target;
FastIOBase(FILE *f): target(f){}
~FastIOBase()=default;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
};
class FastOutput final: public FastIOBase
{
public:
FastOutput(FILE *f=stdout): FastIOBase(f) {}
#ifdef OPENIOBUF
~FastOutput() { flush(); }
void flush() { fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
void put(char x)
{
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE) flush();
#else
putc(x,target);
#endif
}
FastOutput &operator <<(char x)
{ return put(x),*this; }
FastOutput &operator <<(const char *s)
{ for(;*s;put(*(s++)));return *this; }
FastOutput &operator <<(const std::string &s)
{ return (*this)<<s.c_str(); }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastOutput&> operator <<(T x)
{
if(x<0) return put('-'),(*this)<<(-x);
char stk[std::numeric_limits<T>::digits10+1],*top=stk;
do *(top++)=x%10+'0',x/=10; while(x);
while(top!=stk) put(*(--top));
return *this;
}
template<typename ...T>
void writesp(T &&...x)
{ std::initializer_list<int>{((*this)<<(x),put(' '),0)...}; }
template<typename ...T>
void writeln(T &&...x)
{ std::initializer_list<int>{((*this)<<(x),put('\n'),0)...}; }
template<typename Iter>
std::enable_if_t<std::is_base_of<
std::forward_iterator_tag,
typename std::iterator_traits<Iter>::iterator_category>
::value> writesp(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<' '; }
template<typename Iter>
std::enable_if_t<std::is_base_of<
std::forward_iterator_tag,
typename std::iterator_traits<Iter>::iterator_category>
::value> writeln(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<'\n'; }
}qout;
class FastInput final: public FastIOBase
{
private:
bool __eof;
public:
FastInput(FILE *f=stdin): FastIOBase(f),__eof(false)
#ifdef OPENIOBUF
{ buf_p=BUFSIZE; }
void flush() { buf[fread(buf,1,BUFSIZE,target)]=EOF,buf_p=0; }
bool eof()const { return buf[buf_p]==EOF; }
#else
{}
bool eof()const { return feof(target); }
#endif
char get()
{
if(__eof) return EOF;
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
char ch=buf[buf_p++];
#else
char ch=getc(target);
#endif
return ~ch?ch:(__eof=true,EOF);
}
void unget(char c)
{
__eof=false;
#ifdef OPENIOBUF
buf[--buf_p]=c;
#else
ungetc(c,target);
#endif
}
explicit operator bool()const { return !__eof; }
FastInput &operator >>(char &x)
{ while(isspace(x=get()));return *this; }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastInput&> operator >>(T &x)
{
char ch,sym=0;x=0;
while(isspace(ch=get()));
if(__eof) return *this;
if(ch=='-') sym=1,ch=get();
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=get());
return unget(ch),sym?x=-x:x,*this;
}
FastInput &operator >>(char *s)
{
while(isspace(*s=get()));
if(__eof) return *this;
for(;!isspace(*s) && !__eof;*(++s)=get());
return unget(*s),*s='\0',*this;
}
FastInput &operator >>(std::string &s)
{
char str_buf[(1<<8)+1]={0},*p=str_buf;
char *const buf_end=str_buf+(1<<8);
while(isspace(*p=get()));
if(__eof) return *this;
for(s.clear(),p++;;p=str_buf)
{
for(;p!=buf_end && !isspace(*p=get()) && !__eof;p++);
if(p!=buf_end) break;
s.append(str_buf);
}
unget(*p),*p='\0',s.append(str_buf);
return *this;
}
template<typename ...T>
void read(T &&...x)
{ std::initializer_list<int>{((*this)>>(x),0)...}; }
template<typename Iter>
std::enable_if_t<std::is_base_of<
std::forward_iterator_tag,
typename std::iterator_traits<Iter>::iterator_category>
::value> read(Iter begin,Iter end)
{ while(begin!=end) (*this)>>*(begin++); }
}qin;
} // namespace FastIO
using FastIO::qin,FastIO::qout;
using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#define LOG(...) [](auto...){}(__VA_ARGS__)
#else
#define FILEIO(file)
#define LOG(...) fprintf(stderr,__VA_ARGS__)
#endif
constexpr int MAXN=3000;
int n,m;
char s[MAXN+5][MAXN+5];
bool fs[MAXN+5][MAXN+5],ft[MAXN+5][MAXN+5],visa[MAXN+5][MAXN+5],visb[MAXN+5][MAXN+5];
int gs[MAXN+5][MAXN+5],gt[MAXN+5][MAXN+5];
int main()
{
qin>>n>>m;
for(int i=1;i<=n;i++) qin>>(s[i]+1);
fs[1][1]=(s[1][1]=='.');
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='.') fs[i][j]|=fs[i-1][j]|fs[i][j-1];
ft[n][m]=(s[n][m]=='.');
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--)
if(s[i][j]=='.') ft[i][j]|=ft[i+1][j]|ft[i][j+1];
LL all=0,ans=0;
for(int i=1;i<=n;i++)
all+=count(s[i]+1,s[i]+m+1,'.');
if(!fs[n][m]) ans=all*(all-1)/2;
else
{
vector<pair<int,int>> A{{1,1}},B{{1,1}};
for(int x=1,y=1;x!=n || y!=m;)
{
if(ft[x][y+1]) y++;
else x++;
A.emplace_back(x,y);
}
for(int x=1,y=1;x!=n || y!=m;)
{
if(ft[x+1][y]) x++;
else y++;
B.emplace_back(x,y);
}
for(auto &[x,y]: A) visa[x][y]=true;
for(auto &[x,y]: B) visb[x][y]=true;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
gs[i][j]=(visa[i][j] && !visb[i][j]);
if(fs[i][j-1]) gs[i][j]+=gs[i][j-1];
else gs[i][j]+=gs[i-1][j];
}
for(int i=n;i>=1;i--) for(int j=m;j>=1;j--)
{
gt[i][j]=(visa[i][j] && !visb[i][j]);
if(ft[i+1][j]) gt[i][j]+=gt[i+1][j];
else gt[i][j]+=gt[i][j+1];
}
LL cnt=0;
for(auto &[x,y]: B)
{
if(visa[x][y]) { cnt++;continue; }
int xx=x-1,yy=y+1;
while(!(fs[xx][yy] && ft[xx][yy]) && xx>=1 && yy<=m)
xx--,yy++;
assert(xx>=1 && yy<=m);
ans+=(gs[xx][yy]+gt[xx][yy]-visa[xx][yy]);
}
ans+=cnt*(all-cnt)+cnt*(cnt-1)/2;
}
qout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5912kb
input:
3 3 ... ... ...
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5712kb
input:
3 3 .** .*. ...
output:
15
result:
ok 1 number(s): "15"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7920kb
input:
3 4 **** .... ****
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
5 5 *.... .*.*. ***** *.*** ..*..
output:
66
result:
ok 1 number(s): "66"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5596kb
input:
10 10 ...***.*.. **...*.*** ...***.*.. .**...*.*. .*****..*. ..*.****.* .**...**** ..*..*.*.* *.*.**.... ....**...*
output:
1378
result:
ok 1 number(s): "1378"
Test #6:
score: 0
Accepted
time: 96ms
memory: 118268kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17999999
result:
ok 1 number(s): "17999999"
Test #7:
score: 0
Accepted
time: 100ms
memory: 118476kb
input:
3000 3000 ...................................................................................................................*......................................................................................................................................................................*..........
output:
17981671
result:
ok 1 number(s): "17981671"
Test #8:
score: 0
Accepted
time: 89ms
memory: 118272kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17963615
result:
ok 1 number(s): "17963615"
Test #9:
score: 0
Accepted
time: 79ms
memory: 118396kb
input:
3000 3000 .........................................................................................................*...........................................................................................................................................................................................
output:
17945165
result:
ok 1 number(s): "17945165"
Test #10:
score: 0
Accepted
time: 76ms
memory: 118476kb
input:
3000 3000 ......................................................................................................................................*........................................................................................................................................*.....................
output:
17928211
result:
ok 1 number(s): "17928211"
Test #11:
score: 0
Accepted
time: 78ms
memory: 118280kb
input:
3000 3000 ...........................................*.........................................................................................................................................................................................................................................................
output:
17911522
result:
ok 1 number(s): "17911522"
Test #12:
score: 0
Accepted
time: 103ms
memory: 118260kb
input:
3000 3000 ..............................*................................................................................................................*.....................................................................................................................................................
output:
17892283
result:
ok 1 number(s): "17892283"
Test #13:
score: 0
Accepted
time: 91ms
memory: 118476kb
input:
3000 3000 ................................................................*....*................................................................................................................................................................................*..............................................
output:
17873837
result:
ok 1 number(s): "17873837"
Test #14:
score: 0
Accepted
time: 83ms
memory: 118208kb
input:
3000 3000 ............................................................................................*.............................................................................*.....................................................................................................*....................
output:
17856701
result:
ok 1 number(s): "17856701"
Test #15:
score: 0
Accepted
time: 82ms
memory: 118184kb
input:
3000 3000 ......................................*..........................................................................................................................................................*...................................................................................................
output:
17837857
result:
ok 1 number(s): "17837857"
Test #16:
score: 0
Accepted
time: 88ms
memory: 118476kb
input:
3000 3000 .................................................................................................................................................................................................................................*...................................................................
output:
17819731
result:
ok 1 number(s): "17819731"
Test #17:
score: 0
Accepted
time: 86ms
memory: 118224kb
input:
3000 3000 ......**.....*.......*.*..........*..*...............**.............*.......*......*........*...*.....*.*.................*......*....*.........*....................*.................*.......................*.......*..*.*.......*.......................*..........*..*......................*...
output:
16202000
result:
ok 1 number(s): "16202000"
Test #18:
score: 0
Accepted
time: 137ms
memory: 118252kb
input:
3000 3000 ..................*....*....*...*.*.............*.............*....*.*..*...*...*...*....*.................*...*.*.***...*....*......*.......**...*.......*.*...**...*...*...**.........*..........*.....*.*....*..*.......*.........*..*.....*...............**.......*.....*.*..*.*.*........*.....
output:
21600132
result:
ok 1 number(s): "21600132"
Test #19:
score: 0
Accepted
time: 76ms
memory: 30028kb
input:
3000 3000 ..*.**...*...............*........*.*..*.*.....*........*.*..........***..*..*..*..*.*....*...*.*.....***.*...*........*..*.****..*.*....**.......*......*....*..*......*......*..*..*.*..*....*..**.*.......**.*...*....**.....**..*......*...*....*..*.**.*..***...*.....*....***.*........*.......
output:
19862779430431
result:
ok 1 number(s): "19862779430431"
Test #20:
score: 0
Accepted
time: 88ms
memory: 30232kb
input:
3000 3000 .**.**..***....*.*....*..*...*.**.**.**.......*...*........*.**.*...*...**..*...*.*.**.*.*.*.*..*...*.....*.*.**.*.*....*.**.....*..**.**.*....**.**.**..*..**...*...***.**.*.*......**.**.*...****.....***.*..*.**.*......*..**.**.**.....**...*.*..***.******...**....****..***..**.*........*.....
output:
14601805246666
result:
ok 1 number(s): "14601805246666"
Test #21:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
1 1 *
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
1 1 .
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 0ms
memory: 5896kb
input:
2 2 .. ..
output:
6
result:
ok 1 number(s): "6"
Test #24:
score: 0
Accepted
time: 99ms
memory: 30232kb
input:
3000 3000 .***..**..*.*.*..*...**.*.**...***.....*..***.***.***.*..***.*......*.**.***.***.*...**.*.*..***.*..*.**..***.....*.*...***.*.***.*...*.*.....***.*..**...*.*..*.******.*.*...**.*..**.**.**.*.**..***.**.***..*......**.***.**.*....*..*.....*...*..*.*..*..*.*...**.**...*..**..***.**..*....*.....
output:
10151159625145
result:
ok 1 number(s): "10151159625145"
Test #25:
score: 0
Accepted
time: 37ms
memory: 29740kb
input:
3000 3000 *******************************************************************************************************************************************************************************************************************************************************.******************************************...
output:
39716328
result:
ok 1 number(s): "39716328"
Test #26:
score: 0
Accepted
time: 96ms
memory: 118252kb
input:
3000 3000 ..*..................................................................................................................................................................................................................................................................................................
output:
35988321
result:
ok 1 number(s): "35988321"
Test #27:
score: 0
Accepted
time: 103ms
memory: 118212kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
35981866
result:
ok 1 number(s): "35981866"
Test #28:
score: 0
Accepted
time: 91ms
memory: 118420kb
input:
3000 3000 ...**................................................................................................................................................................................................................................................................................................
output:
17988153
result:
ok 1 number(s): "17988153"
Test #29:
score: 0
Accepted
time: 96ms
memory: 118256kb
input:
3000 3000 ...*.*...............................................................................................................................................................................................................................................................................................
output:
35969654
result:
ok 1 number(s): "35969654"
Test #30:
score: 0
Accepted
time: 105ms
memory: 118272kb
input:
3000 3000 ..*..................................................................................................................................................................................................................................................................................................
output:
17982216
result:
ok 1 number(s): "17982216"
Test #31:
score: 0
Accepted
time: 96ms
memory: 118476kb
input:
3000 3000 ....**.*.............................................................................................................................................................................................................................................................................................
output:
71916090
result:
ok 1 number(s): "71916090"
Test #32:
score: 0
Accepted
time: 86ms
memory: 118244kb
input:
3000 3000 ....****.............................................................................................................................................................................................................................................................................................
output:
71903186
result:
ok 1 number(s): "71903186"
Test #33:
score: 0
Accepted
time: 103ms
memory: 118252kb
input:
3000 3000 .........*...........................................................................................................................................................................................................................................................................................
output:
17973051
result:
ok 1 number(s): "17973051"
Test #34:
score: 0
Accepted
time: 96ms
memory: 118276kb
input:
3000 3000 .*.......*.............................................................................................................*................................................................................*............................................................................................
output:
35630636
result:
ok 1 number(s): "35630636"
Test #35:
score: 0
Accepted
time: 94ms
memory: 118424kb
input:
3000 3000 .**...........................*..........................................................................................................................................*...........................................................................................................................
output:
44529907
result:
ok 1 number(s): "44529907"
Test #36:
score: 0
Accepted
time: 93ms
memory: 118192kb
input:
3000 3000 ....*................................................................................................................................................................................................................................................................................................
output:
53426863
result:
ok 1 number(s): "53426863"
Test #37:
score: 0
Accepted
time: 82ms
memory: 118256kb
input:
3000 3000 ..*.*........................................................................*............................*...............*.............................................................................................................................................*........*...................
output:
53419301
result:
ok 1 number(s): "53419301"
Test #38:
score: 0
Accepted
time: 92ms
memory: 118428kb
input:
3000 3000 ......*.........*...................................................................................*.....................................................................................................................*................................................*.........................
output:
26705269
result:
ok 1 number(s): "26705269"
Test #39:
score: 0
Accepted
time: 98ms
memory: 118404kb
input:
3000 3000 ....*.**....*................*............................*..........*...............................................................................................................................................................................................................................
output:
17799069
result:
ok 1 number(s): "17799069"
Test #40:
score: 0
Accepted
time: 76ms
memory: 118272kb
input:
3000 3000 ...***.......................................*...........*.....................*........*...........................................................................................................................................................*................................................
output:
53393629
result:
ok 1 number(s): "53393629"
Test #41:
score: 0
Accepted
time: 96ms
memory: 118276kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
98852811
result:
ok 1 number(s): "98852811"
Test #42:
score: 0
Accepted
time: 1ms
memory: 7768kb
input:
1 3000 ........................................................................................................................................................................................................................................................................................................
output:
4498500
result:
ok 1 number(s): "4498500"
Test #43:
score: 0
Accepted
time: 80ms
memory: 118260kb
input:
3000 3000 .*.....*...........................................................................................................*...................................*........................................................................................*............*.......................................
output:
88979547
result:
ok 1 number(s): "88979547"
Test #44:
score: 0
Accepted
time: 75ms
memory: 118148kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
35964327
result:
ok 1 number(s): "35964327"