結果

問題 No.3244 Range Multiple of 8 Query
ユーザー ゼリトキ
提出日時 2025-08-22 22:25:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,061 bytes
コンパイル時間 3,207 ms
コンパイル使用メモリ 291,948 KB
実行使用メモリ 15,944 KB
最終ジャッジ日時 2025-08-22 22:25:27
合計ジャッジ時間 11,851 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 3 RE * 3 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

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[N+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);
        if(dat[now_num].size()>=4) 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;
            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]];
                    minus.push_back(plus);
                    if(plus<l) ok=0;
                    rep(l,minus.size()){
                        if(plus>minus[l]) plus--;
                    }
                    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