結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
ユーザー ks2m
提出日時 2021-10-29 23:10:11
言語 Java
(openjdk 23)
結果
AC  
実行時間 518 ms / 4,000 ms
コード長 2,142 bytes
コンパイル時間 2,590 ms
コンパイル使用メモリ 78,764 KB
実行使用メモリ 82,460 KB
最終ジャッジ日時 2024-10-07 12:47:53
合計ジャッジ時間 16,942 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
public class Main {
    static int n, m;
    static int[][] cx, cy;
    static List<Integer> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] x = br.readLine().toCharArray();
        char[] y = br.readLine().toCharArray();
        int q = Integer.parseInt(br.readLine());
        int[] l = new int[q];
        int[] r = new int[q];
        int[] c = new int[q];
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            l[i] = Integer.parseInt(sa[0]) - 1;
            r[i] = Integer.parseInt(sa[1]);
            c[i] = sa[2].charAt(0) - 'a';
        }
        br.close();
        n = x.length;
        cx = new int[26][n + 1];
        for (int i = 0; i < n; i++) {
            cx[x[i] - 'a'][i + 1]++;
            for (int j = 0; j < 26; j++) {
                cx[j][i + 1] += cx[j][i];
            }
        }
        m = y.length;
        cy = new int[26][m + 1];
        for (int i = 0; i < m; i++) {
            cy[y[i] - 'a'][i + 1]++;
            for (int j = 0; j < 26; j++) {
                cy[j][i + 1] += cy[j][i];
            }
        }
        list = new ArrayList<>();
        list.add(n);
        while (true) {
            int cur = list.get(list.size() - 1);
            int next = cur * 2 + m;
            list.add(next);
            if (next > 1000000000) {
                break;
            }
        }
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            int ans = f(r[i], c[i]) - f(l[i], c[i]);
            pw.println(ans);
        }
        pw.flush();
    }
    static int f(int x, int c) {
        int ret = 0;
        boolean[] b = new boolean[40];
        for (int i = list.size() - 1; i >= 0 && x > 0; i--) {
            int len = list.get(i);
            if (x >= len) {
                b[i] = true;
                int v1 = cx[c][n];
                int v2 = 1 << i;
                ret += v1 * v2;
                int v3 = cy[c][m];
                int v4 = v2 - 1;
                ret += v3 * v4;
                x -= len;
                if (x >= m) {
                    ret += v3;
                    x -= m;
                    if (i == 0) {
                        ret += cx[c][n] - cx[c][n - x];
                        x = 0;
                    }
                } else {
                    if (b[i + 1]) {
                        ret += cy[c][m] - cy[c][m - x];
                        x = 0;
                    } else {
                        ret += cy[c][x];
                    }
                    x = 0;
                }
            }
        }
        ret += cx[c][x];
        return ret;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0