GigaCode 2019 F問題 - クローゼットの配置

Source

GigaCode 2019
問題文

問題概要

省略

解法

省略

cLayversion 20191123-1)のコード

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: 2021年09月28日22時02分21秒
Last modified: 2019年11月25日10時58分15秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: