省略
省略
C++に変換後のコードはこちら
int X, Y, N, R, C;
char A[5000][5000];
int w;
int h[5002];
Grid1d<int> b;
int st[5002], p[5002], sts;
{
int res = 0;
rd(X,Y,N);
rep(N){
rd(R--,C--);
A[R][C] = 1;
}
w = Y + 2;
b.malloc(w);
rep(k,X){
rep(i,Y){
h[i+1]++;
if(A[k][i]) h[i+1] = 0;
}
b[0] = b[w-1] = 1;
if(k==X-1){
rep(i,Y) b[i+1] = 1;
} else {
rep(i,Y) b[i+1] = A[k+1][i];
}
b.setSum();
sts = 0;
arrInsert(sts,sts,st,h[0],p,0);
rep(i,1,w){
arrInsert(sts,sts,st,h[i],p,i);
while(sts>=2 && st[sts-2] > st[sts-1]){
if(b.getSum(p[sts-2]+1, p[sts-1]-1) > 0) res++;
arrErase(sts-2, sts, st, p);
}
if(b.getSum(p[sts-2]+1, p[sts-1]-1) > 0) res++;
if(st[sts-2] == st[sts-1]) arrErase(sts-2, sts, st, p);
}
}
wt(res);
}
Current time: 2024年04月23日23時31分41秒
Last modified: 2019年11月25日10時58分15秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る
Logged in as: unknown user (not login)