結果
問題 |
No.1725 [Cherry 3rd Tune D] 無言の言葉
|
ユーザー |
|
提出日時 | 2021-10-29 22:40:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 163 ms / 4,000 ms |
コード長 | 1,922 bytes |
コンパイル時間 | 1,730 ms |
コンパイル使用メモリ | 174,776 KB |
実行使用メモリ | 24,416 KB |
最終ジャッジ日時 | 2024-10-07 12:20:19 |
合計ジャッジ時間 | 6,656 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> #define rep(i, l, r) for (int i = (l); i < (r); i++) using namespace std; typedef long long ll; int main() { string X, Y; int Q; cin >> X >> Y >> Q; int M = X.size(), N = Y.size(); vector<vector<int>> XC(26, vector<int>(M + 1, 0)), YC(26, vector<int>(N + 1, 0)); rep(i, 0, M) { rep(j, 0, 26) XC[j][i + 1] = XC[j][i]; XC[X[i] - 'a'][i + 1]++; } rep(i, 0, N) { rep(j, 0, 26) YC[j][i + 1] = YC[j][i]; YC[Y[i] - 'a'][i + 1]++; } vector<int> L(Q), R(Q); vector<char> C(Q); rep(i, 0, Q) cin >> L[i] >> R[i] >> C[i]; rep(i, 0, Q) { int a = (L[i] - 1) / (M + N), b = (L[i] - 1) % (M + N); int c0 = (XC[C[i] - 'a'][M] + YC[C[i] - 'a'][N]) * a; if (b <= M) { if (a % 2) { c0 += XC[C[i] - 'a'][M] - XC[C[i] - 'a'][M - b]; } else { c0 += XC[C[i] - 'a'][b]; } } else { c0 += XC[C[i] - 'a'][M]; int idx = a + 1; while (idx % 2 == 0) idx /= 2; if (idx % 4 == 3) { c0 += YC[C[i] - 'a'][N] - YC[C[i] - 'a'][N - b + M]; } else { c0 += YC[C[i] - 'a'][b - M]; } } a = R[i] / (M + N), b = R[i] % (M + N); int c1 = (XC[C[i] - 'a'][M] + YC[C[i] - 'a'][N]) * a; if (b <= M) { if (a % 2) { c1 += XC[C[i] - 'a'][M] - XC[C[i] - 'a'][M - b]; } else { c1 += XC[C[i] - 'a'][b]; } } else { c1 += XC[C[i] - 'a'][M]; int idx = a + 1; while (idx % 2 == 0) idx /= 2; if (idx % 4 == 3) { c1 += YC[C[i] - 'a'][N] - YC[C[i] - 'a'][N - b + M]; } else { c1 += YC[C[i] - 'a'][b - M]; } } cout << c1 - c0 << endl; } }