結果
問題 |
No.1725 [Cherry 3rd Tune D] 無言の言葉
|
ユーザー |
👑 ![]() |
提出日時 | 2021-10-16 18:01:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 219 ms / 4,000 ms |
コード長 | 1,138 bytes |
コンパイル時間 | 3,003 ms |
コンパイル使用メモリ | 252,708 KB |
実行使用メモリ | 50,340 KB |
最終ジャッジ日時 | 2024-10-07 09:13:59 |
合計ジャッジ時間 | 9,695 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 42 |
ソースコード
#pragma optimize("avx2") #include <bits/stdc++.h> using namespace std; using i64 = int64_t; int main(){ using A = valarray<i64>; string X, Y; cin >> X >> Y; A countX(i64{}, 27), countY(i64{}, 27); vector<A> accX = {countX}, accY = {countY}; for(char& c : X){ countX[c -= 'a']++; countX[26]++; accX.push_back(countX); } for(char& c : Y){ countY[c -= 'a']++; countY[26]++; accY.push_back(countY); } vector<A> countF = {countX}; for(i64 i = 0; i < 30; i++) countF.push_back(countF.back() * 2 + countY); function<i64(i64, i64, char)> count = [&](i64 N, i64 R, char C){ if(N == 0) return accX[R][C]; if(R < countF[N - 1][26]) return count(N - 1, R, C); if(R > countF[N - 1][26] + Y.size()) return countF[N][C] - count(N - 1, countF[N][26] - R, C); return countF[N - 1][C] + accY[R - countF[N - 1][26]][C]; }; i64 Q; cin >> Q; while(Q--){ i64 L, R; char C; cin >> L >> R >> C; L--; C -= 'a'; cout << count(30, R, C) - count(30, L, C) << '\n'; } }