結果

問題 No.3244 Range Multiple of 8 Query
ユーザー ks2m
提出日時 2025-08-22 23:02:41
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,854 bytes
コンパイル時間 2,886 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 98,488 KB
最終ジャッジ日時 2025-08-22 23:03:11
合計ジャッジ時間 27,813 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int q = Integer.parseInt(sa[1]);
		char[] s = br.readLine().toCharArray();

		List<TreeSet<Integer>> list = new ArrayList<>();
		for (int i = 0; i < 10; i++) {
			list.add(new TreeSet<>());
		}
		for (int i = 0; i < n; i++) {
			int c = s[i] - '0';
			list.get(c).add(i);
		}

		int inf = 1000000000;
		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < q; i++) {
			sa = br.readLine().split(" ");
			int l = Integer.parseInt(sa[0]) - 1;
			int r = Integer.parseInt(sa[1]);
			int ans = inf;
			if (l + 1 == r) {
				if (s[l] == '8') {
					ans = 0;
				}

			} else if (l + 2 == r) {
				int c = (s[l] - '0') * 10 + (s[l + 1] - '0');
				if (c % 8 == 0) {
					ans = 0;
				} else {
					c = (s[l + 1] - '0') * 10 + (s[l] - '0');
					if (c % 8 == 0) {
						ans = 1;
					}
				}

			} else {
				for (int j = 0; j < 1000; j += 8) {
					int val = 0;

					int c1 = j % 10;
					Integer i1 = list.get(c1).lower(r);
					if (i1 == null || i1 < l) {
						continue;
					}
					val += r - 1 - i1;

					int c2 = j / 10 % 10;
					Integer i2 = null;
					if (c1 == c2) {
						i2 = list.get(c2).lower(i1);
						if (i2 == null || i2 < l) {
							continue;
						}
						val += r - 2 - i2;
					} else {
						i2 = list.get(c2).lower(r);
						if (i2 == null || i2 < l) {
							continue;
						}
						if (i1 < i2) {
							if (i2 != r - 1) {
								val += r - 1 - i2;
							}
						} else {
							val += r - 2 - i2;
						}
					}

					int c3 = j / 100 % 10;
					if (c2 == c3) {
						Integer i3 = list.get(c3).lower(i2);
						if (i3 == null || i3 < l) {
							continue;
						}
						if (c1 == c3) {
							val += r - 3 - i3;
						} else {
							if (i1 < i3) {
								if (i3 != r - 2) {
									val += r - 2 - i3;
								}
							} else {
								val += r - 3 - i3;
							}
						}
					} else {
						if (c1 == c3) {
							Integer i3 = list.get(c3).lower(i1);
							if (i3 == null || i3 < l) {
								continue;
							}
							if (i2 < i3) {
								if (i3 != r - 2) {
									val += r - 2 - i3;
								}
							} else {
								val += r - 3 - i3;
							}
						} else {
							Integer i3 = list.get(c3).lower(r);
							if (i3 == null || i3 < l) {
								continue;
							}
							val += r - 3 - i3;
							if (i1 < i3) val++;
							if (i2 < i3) val++;
						}
					}
					ans = Math.min(ans, val);
				}
			}
			if (ans == inf) {
				ans = -1;
			}
			pw.println(ans);
		}
		pw.flush();
		br.close();
	}
}
0