結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー Taiki0715
提出日時 2025-08-30 16:22:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,605 ms / 5,000 ms
コード長 6,575 bytes
コンパイル時間 1,741 ms
コンパイル使用メモリ 119,920 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-08-30 16:23:30
合計ジャッジ時間 29,495 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#include<cstdint>
#include<limits>
#include<type_traits>
#include<concepts>
template<typename T>
constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);}
template<typename T>
constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);}

template<typename T>
constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);}
template<typename T>
constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);}

template<typename T>
constexpr std::enable_if_t<std::is_integral_v<T>,T>floor_pow2(T n){return n==0?0:T(1)<<msb(n);}

template<typename T>
constexpr std::enable_if_t<std::is_integral_v<T>,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);}

template<std::integral T>
constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);}
template<std::integral T>
constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);}
struct VanEmdeBoasTree{
private:
  int n;
  int l,r;
  int s,sl;
  int mask;
  using u64=uint64_t;
  struct veb3{
    u64 aux=0;
    inline void insert(int x){aux|=u64(1)<<x;}
    inline void erase(int x){aux&=~(u64(1)<<x);}
    inline bool empty()const{return aux==0;}
    inline void clear(){aux=0;}
    inline int predecessor(int x)const{
      if(x<0)return -1;
      u64 sh=aux<<(63-x);
      return sh==0?-1:x-__builtin_clzll(sh);
    }
    inline int successor(int x)const{
      u64 sh=aux>>x;
      return sh==0?64:x+__builtin_ctzll(sh);
    }
    inline bool contains(int x)const{return aux>>x&1;}
  };
  struct veb2{
    int l,r;
    int s,sl;
    int mask;
    int mn,mx;
    std::vector<veb3>child;
    veb3 aux;
    veb2(){}
    veb2(int log2n):l(log2n/2),r((log2n+1)/2),s(1<<log2n),sl(1<<(log2n/2)),mask((1<<((log2n+1)/2))-1),mn(1<<log2n),mx(-1){
      child.resize(sl);
    }
    void insert(int x){
      if(x<=mn){
        if(x==mn)return;
        std::swap(x,mn);
        if(x==s)mx=mn;
        if(x>=mx)return;
      }
      else if(x>=mx){
        if(x==mx)return;
        std::swap(x,mx);
        if(x<=mn)return;
      }
      int nx=x>>r;
      if(child[nx].empty())aux.insert(nx);
      child[nx].insert(x&mask);
    }
    void erase(int x){
      if(x<=mn){
        if(x<mn)return;
        x=mn=successor(mn+1);
        if(x>=mx){
          if(x>mx)mx=-1;
          return;
        }
      }
      else if(x>=mx){
        if(x>mx)return;
        x=mx=predecessor(mx-1);
        if(x<=mn)return;
      }
      int nx=x>>r;
      child[nx].erase(x&mask);
      if(child[nx].empty())aux.erase(nx);
    }
    bool empty()const{return mx<mn;}
    void clear(){
      mn=s,mx=-1;
      for(int i=0;i<sl;i++)child[i].clear();
      aux.clear();
    }
    int predecessor(int x)const{
      if(x>=mx)return mx;
      if(x<mn)return -1;
      int nx=x>>r;
      int res=child[nx].predecessor(x&mask);
      if(res>=0)return (nx<<r)+res;
      nx=aux.predecessor(nx-1);
      return nx<0?mn:((nx<<r)+child[nx].predecessor(mask));
    }
    int successor(int x)const{
      if(x<=mn)return mn;
      if(x>mx)return s;
      int nx=x>>r;
      int res=child[nx].successor(x&mask);
      if(res<=mask)return (nx<<r)+res;
      nx=aux.successor(nx+1);
      return nx>=sl?mx:((nx<<r)+child[nx].successor(0));
    }
    inline bool contains(int x)const{return successor(x)==x;}
  };
  std::vector<veb2>child;
  veb2 aux;
  int mn,mx;
  int N;
public:
  VanEmdeBoasTree():mn(0),mx(-1){}
  VanEmdeBoasTree(int n):N(n){
    if(n<16)n=16;
    n=ceil_pow2(n);
    int log2n=msb(n);
    assert(n<=(1<<24));
    mn=-1;
    mx=n;
    l=log2n/2,r=(log2n+1)/2;
    s=1<<log2n,sl=1<<l;
    mask=(1<<r)-1;
    aux=veb2(l);
    child.resize(sl,veb2(r));
  }
  void insert(int x){
    if(x<=mn){
      if(x==mn)return;
      std::swap(x,mn);
      if(x==s)mx=mn;
      if(x>=mx)return;
    }
    else if(x>=mx){
      if(x==mx)return;
      std::swap(x,mx);
      if(x<=mn)return;
    }
    int nx=x>>r;
    if(child[nx].empty())aux.insert(nx);
    child[nx].insert(x&mask);
  }
  void erase(int x){
    if(x<=mn){
      if(x<mn)return;
      x=mn=successor(mn+1);
      if(x>=mx){
        if(x>mx)mx=-1;
        return;
      }
    }
    else if(x>=mx){
      if(x>mx)return;
      x=mx=predecessor(mx-1);
      if(x<=mn)return;
    }
    int nx=x>>r;
    child[nx].erase(x&mask);
    if(child[nx].empty())aux.erase(nx);
  }
  void clear(){
    mn=s,mx=-1;
    for(int i=0;i<sl;i++)child[i].clear();
    aux.clear();
  }
  int predecessor(int x)const{
    if(x>=mx)return mx;
    if(x<mn)return -1;
    int nx=x>>r;
    int res=child[nx].predecessor(x&mask);
    if(res>=0)return (nx<<r)+res;
    nx=aux.predecessor(nx-1);
    return nx<0?mn:((nx<<r)+child[nx].predecessor(mask));
  }
  int successor(int x)const{
    if(x<=mn)return mn;
    if(x>mx)return N;
    int nx=x>>r;
    int res=child[nx].successor(x&mask);
    if(res<=mask)return std::min(N,(nx<<r)+res);
    nx=aux.successor(nx+1);
    return std::min(N,(nx>=sl?mx:((nx<<r)+child[nx].successor(0))));
  }
  inline bool contains(int x)const{return successor(x)==x;}
};
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,q;
  cin>>n>>q;
  string s;
  cin>>s;
  vector<VanEmdeBoasTree>veb(10,VanEmdeBoasTree(n+1));
  for(int i=0;i<10;i++)veb[i].insert(0);
  for(int i=0;i<n;i++)veb[s[i]-'0'].insert(i+1);
  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 {
    l++,r++;
    int cpos=veb[c].predecessor(r-1);
    if(cpos<l)return 1e9;
    int bpos=veb[b].predecessor(b==c?cpos-1:r-1);
    if(bpos<l)return 1e9;
    int apos=veb[a].predecessor(a==b?bpos-1:(a==c?cpos-1:r-1));
    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