結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー ルビサファせだい
提出日時 2025-08-22 22:40:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4,652 ms / 5,000 ms
コード長 2,743 bytes
コンパイル時間 4,056 ms
コンパイル使用メモリ 257,780 KB
実行使用メモリ 8,712 KB
最終ジャッジ日時 2025-08-22 22:41:22
合計ジャッジ時間 74,236 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using ll = long long;
using ull = unsigned long long;
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<>>;
ll ll_min = numeric_limits<ll>::min();
ll ll_max = numeric_limits<ll>::max();
ll ALPHABET_N = 26;
static const ll INF = ll_max / 10;
#define rep(i, n) for (ll i = (ll)0; i < (ll)n; i++)
#define rep_(i, k, n) for (ll i = (ll)k; i < (ll)n; i++)
#define all(a) a.begin(), a.end()

using namespace atcoder;
using mint = modint998244353;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	vector<vector<ll>> num2indices(10);
	rep(i, n)
	{
		num2indices[s[i] - '0'].push_back(i);
	}
	rep(_, q)
	{
		ll l, r;
		cin >> l >> r;
		l--;
		if (r - l == 1)
		{
			cout << (s[l] == '8' ? 0 : -1) << endl;
		}
		else if (r - l == 2)
		{
			string s1 = s.substr(l, 2);
			string s2 = s1;
			reverse(s2.begin(), s2.end());
			ll ans = ll_max;
			ll cur = 16;
			while (cur < 100)
			{
				string s3 = to_string(cur);
				if (s1 == s3)
				{
					ans = 0;
				}
				else if (s2 == s3)
				{
					ans = min(ans, 1LL);
				}
				cur += 8;
			}
			if (ans == ll_max)
			{
				ans = -1;
			}
			cout << ans << endl;
		}
		else
		{
			ll cur = 112;
			ll ans = ll_max;
			while (cur < 1000)
			{
				string s3 = to_string(cur);
				if (any_of(all(s3), [](char c)
						   { return c == '0'; }))
				{
					cur += 8;
					continue;
				}
				char c1 = s3[2], c2 = s3[1], c3 = s3[0];
				auto it1 = lower_bound(all(num2indices[c1 - '0']), r);
				if (it1 == num2indices[c1 - '0'].begin() || *(--it1) < l)
				{
					cur += 8;
					continue;
				}
				auto it2 = lower_bound(all(num2indices[c2 - '0']), r);
				if (it2 == num2indices[c2 - '0'].begin() || *(--it2) < l)
				{
					cur += 8;
					continue;
				}
				if (*it1 == *it2)
				{
					if (it2 == num2indices[c2 - '0'].begin() || *(--it2) < l)
					{
						cur += 8;
						continue;
					}
				}
				auto it3 = lower_bound(all(num2indices[c3 - '0']), r);
				if (it3 == num2indices[c3 - '0'].begin() || *(--it3) < l)
				{
					cur += 8;
					continue;
				}
				if (*it1 == *it3)
				{
					if (it3 == num2indices[c3 - '0'].begin() || *(--it3) < l)
					{
						cur += 8;
						continue;
					}
				}
				if (*it2 == *it3)
				{
					if (it3 == num2indices[c3 - '0'].begin() || *(--it3) < l)
					{
						cur += 8;
						continue;
					}
				}
				ll i = r - *it1 - 1, j = r - *it2 - 1, k = r - *it3 - 1;
				ll ret = i + j + k - 3 + (j < i) + (k < i) + (k < j);
				ans = min(ans, ret);
				cur += 8;
			}
			if (ans == ll_max)
			{
				ans = -1;
			}
			cout << ans << endl;
		}
	}

	return 0;
}
0