結果
問題 |
No.3244 Range Multiple of 8 Query
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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'; } } }