結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー ゼリトキ
提出日時 2025-08-22 22:59:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,385 ms / 5,000 ms
コード長 2,686 bytes
コンパイル時間 3,604 ms
コンパイル使用メモリ 298,296 KB
実行使用メモリ 8,184 KB
最終ジャッジ日時 2025-08-22 23:00:29
合計ジャッジ時間 31,794 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ll long long
const long long mod=998244353;
const long long hmod=46216567629137;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);


    //入力
    int N,Q;
    cin>>N>>Q;
    string S;
    cin>>S;
    int ans[Q+1];
    pair<pair<int,int>,int>lr[Q+1];
    for(int i=1;i<=Q;i++){
        cin>>lr[i].first.second>>lr[i].first.first;
        lr[i].second=i;
    }


    //前計算等
    sort(lr+1,lr+Q+1);
    int place=1;
    deque<int>dat[10];
    for(int i=0;i<=9;i++){
        rep(j,3) dat[i].push_front(-1);
    }
    vector<string>check_number;
    for(int i=104;i<1000;i+=8){
        string ss=to_string(i);
        if(ss[0]=='0'||ss[1]=='0'||ss[2]=='0') continue;
        check_number.push_back(ss);
    }
    int cnt[10];
    vector<int>minus;



    for(int i=1;i<=N;i++){
        int now_num=S[i-1]-'0';
        dat[now_num].push_front(i);
        dat[now_num].pop_back();
        while(place<=Q && lr[place].first.first==i){
            int now_ans=1e9;
            int l=lr[place].first.second,r=lr[place].first.first;
            if(l==r){
                if(S[r-1]=='8') ans[lr[place].second]=0;
                else ans[lr[place].second]=-1;
            }
            else if(r-1==l){
                int a=(S[l-1]-'0')*10+(S[r-1]-'0');
                if(a%8==0) ans[lr[place].second]=0;
                else{
                    a=(S[r-1]-'0')*10+(S[l-1]-'0');
                    if(a%8==0) ans[lr[place].second]=1;
                    else ans[lr[place].second]=-1;
                }
            }
            else{
                for(int j=0;j<check_number.size();j++){
                    for(int k=1;k<=9;k++) cnt[k]=0;
                    bool ok=1;
                    minus.clear();
                    int now_cnt=0;
                    for(int k=2;k>=0;k--){
                        int p=check_number[j][k]-'0';
                        int plus=dat[p][cnt[p]];
                        if(plus<l) ok=0;
                        rep(m,minus.size()){
                            if(plus>minus[m]) plus--;
                        }
                        minus.push_back(plus);
                        sort(minus.rbegin(),minus.rend());
                        now_cnt+=(r-(2-k))-plus;
                        cnt[p]++;
                    }
                    if(ok) now_ans=min(now_ans,now_cnt);
                }
                ans[lr[place].second]=now_ans;
            }
            place++;
        }
    }
    
    for(int i=1;i<=Q;i++){
        if(ans[i]==1e9) cout<<"-1\n";
        else cout<<ans[i]<<"\n";
    }
    return 0;
}
0