結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
ユーザー 👑 NachiaNachia
提出日時 2021-10-29 22:06:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,258 bytes
コンパイル時間 1,090 ms
コンパイル使用メモリ 85,336 KB
実行使用メモリ 24,312 KB
最終ジャッジ日時 2024-10-07 11:27:17
合計ジャッジ時間 3,825 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 AC 45 ms
6,820 KB
testcase_38 AC 44 ms
6,820 KB
testcase_39 AC 44 ms
6,820 KB
testcase_40 AC 43 ms
6,816 KB
testcase_41 AC 44 ms
6,820 KB
testcase_42 AC 2 ms
6,816 KB
testcase_43 AC 32 ms
24,312 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/fenwicktree>
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(n); i++)



int main(){
  string str_x, str_y; cin >> str_x >> str_y;
  int num_queries; cin >> num_queries;
  const i64 max_len = 2'000'000'000;

  auto presum_x = vector<vector<int>>(26, vector<int>(str_x.size() + 1, 0));
  for(int i=0; i<str_x.size(); i++){
    for(int c=0; c<26; c++) presum_x[c][i+1] = presum_x[c][i];
    presum_x[str_x[i] - 'a'][i+1] += 1;
  }
  
  auto presum_y = vector<vector<int>>(26, vector<int>(str_y.size() + 1, 0));
  for(int i=0; i<str_y.size(); i++){
    for(int c=0; c<26; c++) presum_y[c][i+1] = presum_y[c][i];
    presum_y[str_y[i] - 'a'][i+1] += 1;
  }

  vector<i64> sizes_of_ranked;
  sizes_of_ranked.push_back(str_x.size());
  while(sizes_of_ranked.back() < max_len){
    i64 prev = sizes_of_ranked.back();
    sizes_of_ranked.push_back(prev * 2 + (i64)str_y.size());
  }

  auto fullsum_ranked = vector<vector<int>>(26, vector<int>(sizes_of_ranked.size(), 0));
  for(int c=0; c<26; c++) fullsum_ranked[c][0] = presum_x[c].back();
  for(int i=1; i<sizes_of_ranked.size(); i++){
    for(int c=0; c<26; c++){
      fullsum_ranked[c][i] = fullsum_ranked[c][i-1] * 2 + presum_y[c].back();
    }
  }

  auto presum_ranked = [&](i64 len, int target_char, auto presum, auto sufsum, int rank = -1)->i64 {
    if(rank == -1) rank = sizes_of_ranked.size() - 1;
    if(rank == 0) return presum_x[target_char][len];
    if(len < sizes_of_ranked[rank-1]){
      return presum(len, target_char, presum, sufsum, rank-1);
    }
    if(len < sizes_of_ranked[rank-1] + (i64)str_y.size()){
      return fullsum_ranked[target_char][rank-1] + presum_y[target_char][len - sizes_of_ranked[rank-1]];
    }
    return fullsum_ranked[target_char][rank-1] + presum_y[target_char].back()
          + sufsum(len - sizes_of_ranked[rank-1] - (i64)str_y.size(), target_char, presum, sufsum, rank-1);
  };

  auto sufsum_ranked = [&](i64 len, int target_char, auto presum, auto sufsum, int rank = -1)->i64 {
    if(rank == -1) rank = sizes_of_ranked.size() - 1;
    if(rank == 0) return presum_x[target_char].back() - presum_x[target_char][str_x.size() - len];
    if(len < sizes_of_ranked[rank-1]){
      return sufsum(len, target_char, presum, sufsum, rank-1);
    }
    if(len < sizes_of_ranked[rank-1] + (i64)str_y.size()){
      return fullsum_ranked[target_char][rank-1] + presum_y[target_char].back() - presum_y[target_char][str_y.size() - (len - sizes_of_ranked[rank-1])];
    }
    return fullsum_ranked[target_char][rank-1] + presum_y[target_char].back()
          + presum(len - sizes_of_ranked[rank-1] - (i64)str_y.size(), target_char, presum, sufsum, rank-1);
  };

  for(int query_idx=0; query_idx < num_queries; query_idx++){
    i64 l, r; char c; cin >> l >> r >> c;
    i64 ans
      = presum_ranked(r, c - 'a', presum_ranked, sufsum_ranked)
      - presum_ranked(l-1, c - 'a', presum_ranked, sufsum_ranked);
    cout << ans << "\n";
  }
  return 0;
}




struct ios_do_not_sync {
    ios_do_not_sync() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0