結果

問題 No.3244 Range Multiple of 8 Query
ユーザー 沙耶花
提出日時 2025-08-22 21:47:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,784 bytes
コンパイル時間 4,276 ms
コンパイル使用メモリ 266,880 KB
実行使用メモリ 312,820 KB
最終ジャッジ日時 2025-08-22 21:48:24
合計ジャッジ時間 34,789 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23 TLE * 1 -- * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:52:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   52 |                 scanf("%d %d",&l,&r);
      |                 ~~~~~^~~~~~~~~~~~~~~

ソースコード

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 Nul;
A op(A a,A b){
	A res = b;
	rep(i,9){
		while(res[i].size()<3 && a[i].size()>0){
			res[i].insert(res[i].begin(),a[i].back());
			a[i].pop_back();
		}
	}
	return res;
}

A e(){
	return Nul;
}

int main(){
	rep(i,9){
		Nul[i] = vector<int>();
	}
	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;
		scanf("%d %d",&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;
			printf("%d\n", ans);
		}
		
	}
}
0