結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
ユーザー LayCurseLayCurse
提出日時 2021-10-29 21:48:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 80 ms / 4,000 ms
コード長 10,308 bytes
コンパイル時間 3,128 ms
コンパイル使用メモリ 217,536 KB
実行使用メモリ 44,416 KB
最終ジャッジ日時 2024-04-16 14:35:40
合計ジャッジ時間 5,957 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 6 ms
5,504 KB
testcase_13 AC 7 ms
5,376 KB
testcase_14 AC 25 ms
6,144 KB
testcase_15 AC 8 ms
6,144 KB
testcase_16 AC 9 ms
6,400 KB
testcase_17 AC 13 ms
6,784 KB
testcase_18 AC 29 ms
6,016 KB
testcase_19 AC 10 ms
5,376 KB
testcase_20 AC 5 ms
5,376 KB
testcase_21 AC 27 ms
5,376 KB
testcase_22 AC 46 ms
17,408 KB
testcase_23 AC 46 ms
16,000 KB
testcase_24 AC 31 ms
12,288 KB
testcase_25 AC 58 ms
24,960 KB
testcase_26 AC 46 ms
20,224 KB
testcase_27 AC 51 ms
27,648 KB
testcase_28 AC 66 ms
27,008 KB
testcase_29 AC 63 ms
25,600 KB
testcase_30 AC 61 ms
30,208 KB
testcase_31 AC 37 ms
15,872 KB
testcase_32 AC 80 ms
40,064 KB
testcase_33 AC 78 ms
41,216 KB
testcase_34 AC 75 ms
38,272 KB
testcase_35 AC 73 ms
34,176 KB
testcase_36 AC 76 ms
37,760 KB
testcase_37 AC 53 ms
5,376 KB
testcase_38 AC 53 ms
5,376 KB
testcase_39 AC 54 ms
5,376 KB
testcase_40 AC 53 ms
5,376 KB
testcase_41 AC 53 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 39 ms
44,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
template<class T> struct cLtraits_identity{
  using type = T;
}
;
template<class T> using cLtraits_try_make_signed =
  typename conditional<
    is_integral<T>::value,
    make_signed<T>,
    cLtraits_identity<T>
    >::type;
template <class S, class T> struct cLtraits_common_type{
  using tS = typename cLtraits_try_make_signed<S>::type;
  using tT = typename cLtraits_try_make_signed<T>::type;
  using type = typename common_type<tS,tT>::type;
}
;
void*wmem;
char memarr[96000000];
template<class S, class T> inline auto min_L(S a, T b)
-> typename cLtraits_common_type<S,T>::type{
  return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;
}
template<class S, class T> inline auto max_L(S a, T b)
-> typename cLtraits_common_type<S,T>::type{
  return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  walloc1d(arr, x2-x1, mem);
  (*arr) -= x1;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_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 = my_getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i;
  int sz = 0;
  for(;;){
    i = my_getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = my_getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(unsigned x){
  int s=0;
  char f[10];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(unsigned long long x){
  int s=0;
  char f[21];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
int WRITER_DOUBLE_DIGIT = 15;
inline int writerDigit_double(){
  return WRITER_DOUBLE_DIGIT;
}
inline void writerDigit_double(int d){
  WRITER_DOUBLE_DIGIT = d;
}
inline void wt_L(double x){
  const int d = WRITER_DOUBLE_DIGIT;
  int k;
  int r;
  double v;
  if(x!=x || (x==x+1 && x==2*x)){
    my_putchar_unlocked('E');
    my_putchar_unlocked('r');
    my_putchar_unlocked('r');
    return;
  }
  if(x < 0){
    my_putchar_unlocked('-');
    x = -x;
  }
  x += 0.5 * pow(0.1, d);
  r = 0;
  v = 1;
  while(x >= 10*v){
    v *= 10;
    r++;
  }
  while(r >= 0){
    r--;
    k = floor(x / v);
    if(k >= 10){
      k = 9;
    }
    if(k <= -1){
      k = 0;
    }
    x -= k * v;
    v *= 0.1;
    my_putchar_unlocked(k + '0');
  }
  if(d > 0){
    my_putchar_unlocked('.');
    v = 1;
    for(r=(0);r<(d);r++){
      v *= 0.1;
      k = floor(x / v);
      if(k >= 10){
        k = 9;
      }
      if(k <= -1){
        k = 0;
      }
      x -= k * v;
      my_putchar_unlocked(k + '0');
    }
  }
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    my_putchar_unlocked(c[i]);
  }
}
inline void wt_L(string &x){
  int i=0;
  for(i=0;x[i]!='\0';i++){
    my_putchar_unlocked(x[i]);
  }
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
template<class T> struct Arr1d{
  int n;
  int mem;
  T*d;
  T& operator[](int a){
    return d[a];
  }
  void sort(){
    reset();
    std::sort(d, d+n);
  }
  int set_cumulative_sum;
  int cumulative_sum_mem;
  T*cumulative_sum;
  void setSum(void){
    int i;
    set_cumulative_sum = 1;
    if(cumulative_sum_mem < n+1){
      delete[] cumulative_sum;
      cumulative_sum = new T[n+1];
      cumulative_sum_mem = n+1;
    }
    cumulative_sum[0] = 0;
    for(i=(0);i<(n);i++){
      cumulative_sum[i+1] = cumulative_sum[i] + d[i];
    }
  }
  T getSum(int i, int j){
    if(set_cumulative_sum==0){
      setSum();
    }
    return cumulative_sum[j+1] - cumulative_sum[i];
  }
  void reset(){
    set_cumulative_sum = 0;
  }
  void constructor(){
    n = mem = 0;
    d = NULL;
    set_cumulative_sum = 0;
    cumulative_sum_mem = 0;
    cumulative_sum = NULL;
  }
  void destructor(){
    delete[] d;
    d = NULL;
    mem = n = 0;
    set_cumulative_sum = 0;
    cumulative_sum_mem = 0;
    delete[] cumulative_sum;
    cumulative_sum = NULL;
  }
  void constructor(int nn){
    constructor();
    malloc(nn);
  }
  void memory_expand(int nn){
    if(mem < nn){
      delete[] d;
      d = new T[nn];
      mem = nn;
    }
  }
  void malloc(int nn){
    reset();
    memory_expand(nn);
    n = nn;
  }
  void setN(int nn){
    reset();
    memory_expand(nn);
    n = nn;
  }
  void setN(int nn, T val){
    int i;
    reset();
    memory_expand(nn);
    n = nn;
    for(i=(0);i<(n);i++){
      d[i] = val;
    }
  }
  template<class S> void set(vector<S> &a){
    int i;
    int nn = a.size();
    setN(nn);
    for(i=(0);i<(nn);i++){
      d[i] = a[i];
    }
  }
  template<class S> void set_c(vector<S> a){
    int i;
    int nn = a.size();
    setN(nn);
    for(i=(0);i<(nn);i++){
      d[i] = a[i];
    }
  }
  template<class S> void set(int nn, S a[]){
    int i;
    setN(nn);
    for(i=(0);i<(nn);i++){
      d[i] = a[i];
    }
  }
  void free(){
    destructor();
  }
  Arr1d(){
    constructor();
  }
  Arr1d(int nn){
    constructor(nn);
  }
  ~Arr1d(){
    destructor();
  }
}
;
int Q;
int L;
int R;
int Xs;
int Ys;
char X[100000+2];
char Y[100000+2];
char C;
Arr1d<int> xx[26];
Arr1d<int> yy[26];
long long len[100];
long long cnt[26][100];
int solve(long long L, long long R, int k, int d){
  int res = 0;
  long long x;
  long long y;
  if(R < Xs){
    return xx[k].getSum(L, R);
  }
  if(L==0 && R==len[d]-1){
    return cnt[k][d];
  }
  x =max_L(L, 0);
  y =min_L(R, len[d-1]-1);
  if(x <= y){
    res += solve(x, y, k, d-1);
  }
  x =max_L(L-len[d-1], 0);
  y =min_L(R-len[d-1], Ys-1);
  if(x <= y){
    res += yy[k].getSum(x, y);
  }
  x =max_L(L-len[d-1]-Ys, 0);
  y =min_L(R-len[d-1]-Ys, len[d-1]-1);
  if(x <= y){
    res += solve(len[d-1]-1-y, len[d-1]-1-x, k, d-1);
  }
  return res;
}
int main(){
  int i, jZyWAPpY, k;
  wmem = memarr;
  Xs = rd(X);
  Ys = rd(Y);
  rd(Q);
  for(k=(0);k<(26);k++){
    int i;
    xx[k].setN(Xs);
    for(i=(0);i<(Xs);i++){
      if(X[i]=='a'+k){
        xx[k][i] =1;
      }
      else{
        xx[k][i] =0;
      }
    }
    yy[k].setN(Ys);
    for(i=(0);i<(Ys);i++){
      if(Y[i]=='a'+k){
        yy[k][i] =1;
      }
      else{
        yy[k][i] =0;
      }
    }
  }
  len[0] = Xs;
  for(k=(0);k<(26);k++){
    cnt[k][0] = xx[k].getSum(0,Xs-1);
  }
  for(i=(1);i<(100);i++){
    len[i] = 2 * len[i-1] + Ys;
    chmin(len[i], 4611686016279904256LL);
    for(k=(0);k<(26);k++){
      cnt[k][i] = 2 * cnt[k][i-1] + yy[k].getSum(0,Ys-1);
      chmin(cnt[k][i], 4611686016279904256LL);
    }
  }
  for(jZyWAPpY=(0);jZyWAPpY<(Q);jZyWAPpY++){
    rd(L);L += (-1);
    rd(R);R += (-1);
    rd(C);
    wt_L(solve(L, R, C-'a', 34));
    wt_L('\n');
  }
  return 0;
}
// cLay version 20211024-1

// --- original code ---
// int Q, L, R;
// int Xs, Ys;
// char X[1d5+2], Y[1d5+2], C;
// Arr1d<int> xx[26], yy[26];
// ll len[100], cnt[26][100];
// 
// int solve(ll L, ll R, int k, int d){
//   int res = 0;
//   ll x, y;
// 
//   // wt(L,R,k,d);
//   if(R < Xs) return xx[k].getSum(L, R);
//   if(L==0 && R==len[d]-1) return cnt[k][d];
//   
//   x = max(L, 0);
//   y = min(R, len[d-1]-1);
//   if(x <= y) res += solve(x, y, k, d-1);
//   
//   x = max(L-len[d-1], 0);
//   y = min(R-len[d-1], Ys-1);
//   if(x <= y) res += yy[k].getSum(x, y);
//   
//   x = max(L-len[d-1]-Ys, 0);
//   y = min(R-len[d-1]-Ys, len[d-1]-1);
//   if(x <= y) res += solve(len[d-1]-1-y, len[d-1]-1-x, k, d-1);
//   
//   return res;
// }
// 
// {
//   rd(X@Xs, Y@Ys, Q);
//   rep(k,26){
//     xx[k].setN(Xs);
//     rep(i,Xs) xx[k][i] = if[X[i]=='a'+k, 1, 0];
//     yy[k].setN(Ys);
//     rep(i,Ys) yy[k][i] = if[Y[i]=='a'+k, 1, 0];
//   }
// 
//   len[0] = Xs;
//   rep(k,26) cnt[k][0] = xx[k].getSum(0,Xs-1);
//   rep(i,1,100){
//     len[i] = 2 * len[i-1] + Ys;
//     len[i] <?= ll_inf;
//     rep(k,26){
//       cnt[k][i] = 2 * cnt[k][i-1] + yy[k].getSum(0,Ys-1);
//       cnt[k][i] <?= ll_inf;
//     }
//   }
// 
//   rep(Q){
//     rd(L--, R--, C);
//     wt(solve(L, R, C-'a', 34));
//   }
// }
0