結果
問題 |
No.3244 Range Multiple of 8 Query
|
ユーザー |
![]() |
提出日時 | 2025-08-22 21:32:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,717 ms / 5,000 ms |
コード長 | 2,650 bytes |
コンパイル時間 | 4,256 ms |
コンパイル使用メモリ | 262,304 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-22 21:34:25 |
合計ジャッジ時間 | 78,105 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 40 |
ソースコード
#include "atcoder/fenwicktree.hpp" #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using isize = size_t; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using f64 = long double; using p2 = pair<i64, i64>; using el = tuple<i64, i64, i64>; using mint = atcoder::modint998244353; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } i64 pow(i64 x, i64 n) { i64 res = 1; i64 t = x; while (n > 0) { if (n & 1) { res = res * t; } t = t * t; n >>= 1; } return res; } i64 pow(i64 x, i64 n, i64 m) { i64 res = 1; i64 t = x % m; while (n > 0) { if (n & 1) { res = res * t % m; } t = t * t % m; n >>= 1; } return res; } void _main() { i64 n, q; cin >> n >> q; string s; cin >> s; vector<vector<i32>> idx(10); for (i64 i = 0; i < n; i++) { idx[s[i] - '0'].push_back(i); } for (;q--;) { i64 l, r; cin >> l >> r; l--; if (r - l == 1) { if (s[l] == '8') { cout << "0\n"; } else { cout << "-1\n"; } continue; } if (r - l == 2) { i64 x = (s[l] - '0') * 10 + s[l + 1] - '0'; i64 y = (s[l + 1] - '0') * 10 + s[l] - '0'; if (x % 8 == 0) { cout << "0\n"; } else if (y % 8 == 0){ cout << "1\n"; } else { cout << "-1\n"; } continue; } vector<i32> lim(10, n); for (i64 i = 0; i < 10; i++) { lim[i] = lower_bound(idx[i].begin(), idx[i].end(), r) - idx[i].begin(); } vector<i32> cnt(10, 0); i32 ans = 1e9; for (i32 i = 104; i < 1000; i += 8) { bool ok = true; vector<pair<i32, i32>> v; i32 m = i; for (i32 j = 2; j >= 0; j--) { i32 x = m % 10; m /= 10; i32 k = lim[x] - cnt[x] - 1; if (k < 0 || idx[x][k] < l) { ok = false; } else { v.push_back({idx[x][k], j}); } cnt[x]++; } m = i; for (i32 j = 2; j >= 0; j--) { i32 x = m % 10; m /= 10; cnt[x]--; } if (!ok) continue; i32 sum = 0; sort(v.begin(), v.end()); for (i64 j = 0; j < v.size(); j++) { sum += r - v[j].first - 1 - (v.size() - j - 1); } sort(v.begin(), v.end(), [&](p2 a, p2 b){return a.second < b.second;}); if (v[0].first > v[1].first) sum++; if (v[1].first > v[2].first) sum++; if (v[0].first > v[2].first) sum++; ans = min(ans, sum); } cout << (ans == 1e9 ? -1 : ans) << "\n"; } }