結果

問題 No.3244 Range Multiple of 8 Query
ユーザー Taiki0715
提出日時 2025-08-30 16:13:09
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,511 bytes
コンパイル時間 1,257 ms
コンパイル使用メモリ 104,040 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-30 16:14:27
合計ジャッジ時間 72,921 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 34 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,q;
  cin>>n>>q;
  string s;
  cin>>s;
  vector<vector<int>>idx(10);
  for(int i=0;i<10;i++){
    idx[i].push_back(-2);
    idx[i].push_back(-1);
  }
  for(int i=0;i<n;i++){
    idx[s[i]-'0'].push_back(i);
  }
  auto naive=[&](string x)->int {
    if(ssize(x)==1)return (x[0]-'0')%8==0?0:-1;
    assert(ssize(x)==2);
    int now=(x[0]-'0')*10+x[1]-'0';
    if(now%8==0)return 0;
    now=(x[1]-'0')*10+x[0]-'0';
    if(now%8==0)return 1;
    return -1;
  };
  auto solve=[&](int l,int r,int a,int b,int c)->int {
    int cpos=*prev(lower_bound(idx[c].begin(),idx[c].end(),r));
    if(cpos<l)return 1e9;
    int bpos=*prev(lower_bound(idx[b].begin(),idx[b].end(),b==c?cpos:r));
    if(bpos<l)return 1e9;
    int apos=*prev(lower_bound(idx[a].begin(),idx[a].end(),a==b?bpos:(a==c?cpos:r)));
    if(apos<l)return 1e9;
    int res=0;
    res+=r-1-cpos;
    if(bpos>cpos)bpos--;
    if(apos>cpos)apos--;
    res+=r-2-bpos;
    if(apos>bpos)apos--;
    res+=r-3-apos;
    return res;
  };
  while(q--){
    int l,r;
    cin>>l>>r;
    l--;
    if(r-l<=2)cout<<naive(s.substr(l,r-l))<<'\n';
    else{
      int ans=1e9;
      for(int x=0;x<1000;x+=8){
        int a=x/100;
        int b=(x/10)%10;
        int c=x%10;
        int now=solve(l,r,a,b,c);
        if(ans>now)ans=now;
      }
      if(ans==(int)1e9)ans=-1;
      cout<<ans<<'\n';
    }
  }
}
0