結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー 沙耶花
提出日時 2025-08-22 21:44:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,810 bytes
コンパイル時間 4,410 ms
コンパイル使用メモリ 268,312 KB
実行使用メモリ 312,504 KB
最終ジャッジ日時 2025-08-22 21:45:36
合計ジャッジ時間 31,408 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 TLE * 3 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000005
#define Inf64 1000000000000000001LL
using A = array<vector<int>,9>;

A op(A a,A b){
	A res = a;
	rep(i,9){
		rep(j,b[i].size())res[i].push_back(b[i][j]);
		sort(res[i].rbegin(), res[i].rend());
		while(res[i].size()>3)res[i].pop_back();
		reverse(res[i].begin(),res[i].end());
	}
	return res;
}

A e(){
	A res;
	rep(i,9)res[i] = {};
	return res;
}

int main(){
	vector<vector<int>> li;
	rep(i,1000){
		if(i<100)continue;
		if(i%8!=0)continue;
		auto x = to_string(i);
		if(x[1]=='0' || x[2]=='0')continue;
		li.push_back({x[0]-'1',x[1]-'1',x[2]-'1'});
	}
	
	int n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	vector<A> a(n);
	rep(i,n){
		a[i] = e();
		a[i][s[i]-'1'].push_back(i);
	}
	segtree<A,op,e> seg(a);
	rep(_,q){
		int l,r;
		cin>>l>>r;
		l--;
		if(r-l==1){
			int t = s[l]-'0';
			if(t%8==0)cout<<0<<endl;
			else cout<<-1<<endl;
		}
		else if(r-l==2){
			int x = s[l]-'0',y = s[l+1]-'0';
			if((x*10+y)%8==0)cout<<0<<endl;
			else if((y*10+x)%8==0)cout<<1<<endl;
			else cout<<-1<<endl;
		}
		else{
			auto res = seg.prod(l,r);
			int ans = Inf32;
			rep(i,li.size()){
				auto tr = res;
				vector<int> tt;
				for(int j=2;j>=0;j--){
					if(tr[li[i][j]].size()>0){
						tt.push_back(tr[li[i][j]].back());
						tr[li[i][j]].pop_back();
					}
					else{
						break;
					}
				}
				if(tt.size()!=3)continue;
				reverse(tt.begin(),tt.end());
				int cur = 0;
				rep(j,3){
					for(int k=j+1;k<3;k++){
						if(tt[j]>tt[k])cur++;
					}
				}
				rep(j,3){
					cur += r-3 + j;
					cur -= tt[j];
				}
				ans = min(ans,cur);
			}
			if(ans==Inf32)ans = -1;
			cout<<ans<<endl;
		}
		
	}
}
0