結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
ユーザー NachiaNachia
提出日時 2021-10-29 22:14:04
言語 C++17
(gcc 11.2.0 + boost 1.78.0)
結果
AC  
実行時間 76 ms / 4,000 ms
コード長 3,258 Byte
コンパイル時間 844 ms
使用メモリ 23,972 KB
最終ジャッジ日時 2021-12-31 04:39:33
合計ジャッジ時間 4,739 ms
ジャッジサーバーID
(参考情報)
judge14 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 1 ms
3,452 KB
testcase_01 AC 2 ms
3,528 KB
testcase_02 AC 2 ms
3,484 KB
testcase_03 AC 2 ms
3,504 KB
testcase_04 AC 1 ms
3,564 KB
testcase_05 AC 2 ms
3,652 KB
testcase_06 AC 4 ms
3,536 KB
testcase_07 AC 2 ms
3,548 KB
testcase_08 AC 3 ms
3,548 KB
testcase_09 AC 1 ms
3,512 KB
testcase_10 AC 2 ms
3,544 KB
testcase_11 AC 2 ms
3,560 KB
testcase_12 AC 4 ms
4,212 KB
testcase_13 AC 5 ms
4,376 KB
testcase_14 AC 21 ms
4,136 KB
testcase_15 AC 5 ms
4,444 KB
testcase_16 AC 6 ms
4,652 KB
testcase_17 AC 9 ms
4,952 KB
testcase_18 AC 25 ms
4,224 KB
testcase_19 AC 8 ms
3,960 KB
testcase_20 AC 4 ms
3,656 KB
testcase_21 AC 23 ms
3,780 KB
testcase_22 AC 39 ms
9,888 KB
testcase_23 AC 35 ms
9,208 KB
testcase_24 AC 27 ms
7,408 KB
testcase_25 AC 49 ms
13,416 KB
testcase_26 AC 43 ms
11,204 KB
testcase_27 AC 47 ms
15,388 KB
testcase_28 AC 60 ms
14,628 KB
testcase_29 AC 52 ms
13,824 KB
testcase_30 AC 50 ms
16,108 KB
testcase_31 AC 32 ms
9,060 KB
testcase_32 AC 66 ms
21,192 KB
testcase_33 AC 76 ms
21,916 KB
testcase_34 AC 73 ms
20,368 KB
testcase_35 AC 59 ms
18,284 KB
testcase_36 AC 63 ms
20,000 KB
testcase_37 AC 47 ms
3,528 KB
testcase_38 AC 47 ms
3,532 KB
testcase_39 AC 46 ms
3,460 KB
testcase_40 AC 46 ms
3,548 KB
testcase_41 AC 47 ms
3,536 KB
testcase_42 AC 2 ms
3,520 KB
testcase_43 AC 31 ms
23,972 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