結果

問題 No.866 レベルKの正方形
ユーザー LayCurseLayCurse
提出日時 2019-08-16 22:05:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,645 bytes
コンパイル時間 2,230 ms
コンパイル使用メモリ 204,292 KB
実行使用メモリ 420,512 KB
最終ジャッジ日時 2024-09-22 16:46:30
合計ジャッジ時間 10,280 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
420,512 KB
testcase_01 AC 3 ms
6,816 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(char &c){
  int i;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i, sz=0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int X;
int Y;
int K;
char C[2000][2002];
long long g[13][2001][2001];
inline long long getSum(int k, int i, int j, int v){
  return g[k][i+v][j+v] - g[k][i][j+v] - g[k][i+v][j] + g[k][i][j];
}
int main(){
  int a, b, c, i, j, k, mn, mx, res=0;
  long long x;
  rd(X);
  rd(Y);
  rd(K);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<(X);Lj4PdHRW++){
      rd(C[Lj4PdHRW]);
    }
  }
  for(i=0;i<(X);i++){
    for(j=0;j<(Y);j++){
      C[i][j] -= 'a';
    }
  }
  for(k=0;k<(13);k++){
    for(i=0;i<(X);i++){
      for(j=0;j<(Y);j++){
        g[k][i+1][j+1] = g[k][i+1][j] + g[k][i][j+1] - g[k][i][j];
        if(C[i][j]==2*k){
          g[k][i+1][j+1]++;
        }
        if(C[i][j]==2*k+1){
          g[k][i+1][j+1] += (1LL<<32);
        }
      }
    }
  }
  for(i=0;i<(X);i++){
    for(j=0;j<(Y);j++){
      int FmcKpFmN, Q5VJL1cS, RZTsC2BF, cTE1_r3A, e98WHCEY, xr20shxY;
      mn = 1;
      mx =min_L(X-i, Y-j);
      Q5VJL1cS = mn;
      e98WHCEY = mx+1;
      while(Q5VJL1cS < e98WHCEY){
        if((Q5VJL1cS + e98WHCEY)%2==0){
          cTE1_r3A = (Q5VJL1cS + e98WHCEY) / 2;
        }
        else{
          cTE1_r3A = (Q5VJL1cS + e98WHCEY - 1) / 2;
        }
        c = 0;
        for(k=0;k<(13);k++){
          x = getSum(k,i,j,cTE1_r3A);
          if(x%(1LL<<32)){
            c++;
          }
          if(x/(1LL<<32)){
            c++;
          }
        }
        if(c >= K){
          e98WHCEY = cTE1_r3A;
        }
        else{
          Q5VJL1cS = cTE1_r3A + 1;
        }
      }
      a =e98WHCEY;
      if(a == mx+1){
        continue;
      }
      RZTsC2BF = a-1;
      FmcKpFmN = mx;
      while(RZTsC2BF < FmcKpFmN){
        if((RZTsC2BF + FmcKpFmN)%2==0){
          xr20shxY = (RZTsC2BF + FmcKpFmN) / 2;
        }
        else{
          xr20shxY = (RZTsC2BF + FmcKpFmN + 1) / 2;
        }
        c = 0;
        for(k=0;k<(13);k++){
          x = getSum(k,i,j,xr20shxY);
          if(x%(1LL<<32)){
            c++;
          }
          if(x/(1LL<<32)){
            c++;
          }
        }
        if(c <= K){
          RZTsC2BF = xr20shxY;
        }
        else{
          FmcKpFmN = xr20shxY - 1;
        }
      }
      b =FmcKpFmN;
      res += b-a+1;
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190810-2

// --- original code ---
// int X, Y, K;
// char C[2000][2002];
// 
// ll g[13][2001][2001];
// 
// inline ll getSum(int k, int i, int j, int v){
//   return g[k][i+v][j+v] - g[k][i][j+v] - g[k][i+v][j] + g[k][i][j];
// }
// 
// {
//   int i, j, k, c, res = 0;
//   int mn, mx, a, b;
//   ll x;
//   
//   rd(X,Y,K,C(X));
// 
//   rep(i,X) rep(j,Y) C[i][j] -= 'a';
// 
//   rep(k,13) rep(i,X) rep(j,Y){
//     g[k][i+1][j+1] = g[k][i+1][j] + g[k][i][j+1] - g[k][i][j];
//     if(C[i][j]==2k) g[k][i+1][j+1]++;
//     if(C[i][j]==2k+1) g[k][i+1][j+1] += (1LL<<32);
//   }
// 
//   rep(i,X) rep(j,Y){
//     mn = 1;
//     mx = min(X-i, Y-j);
// 
//     a = bsearch_min[int, v, mn, mx+1][
//       c = 0;
//       rep(k,13){
//         x = getSum(k,i,j,v);
//         if(x%(1LL<<32)) c++;
//         if(x/(1LL<<32)) c++;
//       }
//     ](c >= K);
// 
//     if(a == mx+1) continue;
//     
//     b = bsearch_max[int, v, a-1, mx][
//       c = 0;
//       rep(k,13){
//         x = getSum(k,i,j,v);
//         if(x%(1LL<<32)) c++;
//         if(x/(1LL<<32)) c++;
//       }
//     ](c <= K);
// 
//     res += b-a+1;
//   }
// 
//   wt(res);
// }
0