結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
ユーザー 👑 NachiaNachia
提出日時 2021-10-29 22:14:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 77 ms / 4,000 ms
コード長 3,258 bytes
コンパイル時間 896 ms
コンパイル使用メモリ 85,308 KB
実行使用メモリ 24,308 KB
最終ジャッジ日時 2024-04-27 03:59:09
合計ジャッジ時間 4,211 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 3 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 4 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 3 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 4 ms
6,940 KB
testcase_13 AC 5 ms
6,944 KB
testcase_14 AC 21 ms
6,944 KB
testcase_15 AC 6 ms
6,940 KB
testcase_16 AC 6 ms
6,944 KB
testcase_17 AC 10 ms
6,944 KB
testcase_18 AC 24 ms
6,940 KB
testcase_19 AC 8 ms
6,940 KB
testcase_20 AC 4 ms
6,940 KB
testcase_21 AC 23 ms
6,944 KB
testcase_22 AC 41 ms
10,112 KB
testcase_23 AC 33 ms
9,216 KB
testcase_24 AC 27 ms
7,680 KB
testcase_25 AC 50 ms
13,580 KB
testcase_26 AC 42 ms
11,392 KB
testcase_27 AC 46 ms
15,232 KB
testcase_28 AC 60 ms
14,812 KB
testcase_29 AC 54 ms
14,004 KB
testcase_30 AC 50 ms
16,412 KB
testcase_31 AC 32 ms
9,216 KB
testcase_32 AC 65 ms
21,268 KB
testcase_33 AC 77 ms
22,140 KB
testcase_34 AC 72 ms
20,628 KB
testcase_35 AC 60 ms
18,500 KB
testcase_36 AC 64 ms
20,152 KB
testcase_37 AC 46 ms
6,944 KB
testcase_38 AC 46 ms
6,944 KB
testcase_39 AC 46 ms
6,940 KB
testcase_40 AC 46 ms
6,944 KB
testcase_41 AC 46 ms
6,940 KB
testcase_42 AC 2 ms
6,940 KB
testcase_43 AC 32 ms
24,308 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 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].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()
          + sufsum(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