結果
問題 |
No.3244 Range Multiple of 8 Query
|
ユーザー |
![]() |
提出日時 | 2025-08-22 21:28:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,746 bytes |
コンパイル時間 | 3,960 ms |
コンパイル使用メモリ | 264,420 KB |
実行使用メモリ | 9,224 KB |
最終ジャッジ日時 | 2025-08-22 21:29:50 |
合計ジャッジ時間 | 30,380 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 TLE * 2 |
ソースコード
#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<i64>> 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<i64> 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<i64> cnt(10, 0); i64 ans = 1e18; for (i64 i = 100; i < 1000; i++) { if (i % 8 != 0) continue; string t = to_string(i); assert(t.size() == 3); bool ok = true; vector<p2> v; for (i64 j = t.size() - 1; j >= 0; j--) { i64 x = t[j] - '0'; i64 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]++; } for (i64 j = t.size() - 1; j >= 0; j--) { i64 x = t[j] - '0'; cnt[x]--; } if (!ok) continue; i64 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.size() >= 2 && v[0].first > v[1].first) sum++; if (v.size() >= 3 && v[1].first > v[2].first) sum++; if (v.size() >= 3 && v[0].first > v[2].first) sum++; ans = min(ans, sum); } cout << (ans == 1e18 ? -1 : ans) << "\n"; } }