結果

問題 No.3244 Range Multiple of 8 Query
ユーザー 沙耶花
提出日時 2025-08-22 22:04:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 736 ms / 5,000 ms
コード長 1,989 bytes
コンパイル時間 5,306 ms
コンパイル使用メモリ 335,556 KB
実行使用メモリ 22,728 KB
最終ジャッジ日時 2025-08-22 22:05:18
合計ジャッジ時間 20,547 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:61:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |                 scanf("%d %d",&ls[i],&rs[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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>;

vector<vector<int>> li;
int tt[3];
int get(array<vector<int>, 9> res){
	int ans = Inf32;
	vector<int> pos(9);
	
	rep(i,li.size()){
		rep(i,9)pos[i] = (int)res[i].size()-1;
		int ci = 0;
		for(int j=2;j>=0;j--){
			if(pos[li[i][j]]>=0){
				tt[2-ci] = res[li[i][j]][pos[li[i][j]]];
				pos[li[i][j]]--;
				ci++;
			}
			else{
				break;
			}
		}
		if(ci!=3)continue;
		int cur = 0;
		rep(j,3){
			for(int k=j+1;k<3;k++){
				if(tt[j]>tt[k])cur++;
			}
		}
		rep(j,3){
			cur -= tt[j];
		}
		ans = min(ans,cur);
	}
	return ans;
}

int main(){
	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<int> ls(q),rs(q);
	vector<vector<int>> is(n);
	rep(i,q){
		scanf("%d %d",&ls[i],&rs[i]);
		ls[i]--;
		is[rs[i]-1].push_back(i);
	}
	A temp;
	rep(i,9)temp[i].clear();
	vector<int> ans(q,-1);
	rep(i,n){
		int d = s[i]-'1';
		temp[s[i]-'1'].push_back(i);
		if(temp[d].size()==4)temp[d].erase(temp[d].begin());
		rep(j,is[i].size()){
			int ii = is[i][j];
			if(rs[ii]-ls[ii]==1){
				int x = s[ls[ii]]-'0';
				if(x%8==0)ans[ii] = 0;
				else ans[ii] = -1;
				continue;
			}
			if(rs[ii]-ls[ii]==2){
				int x = s[ls[ii]]-'0',y = s[ls[ii]+1]-'0';
				if((x*10+y)%8==0)ans[ii] = 0;
				else if((y*10+x)%8==0)ans[ii] = 1;
				else ans[ii] = -1;
				continue;
			}
			auto tt = temp;
			rep(k,9){
				while(tt[k].size()>0 && tt[k][0] < ls[ii]){
					tt[k].erase(tt[k].begin());
				}
			}
			int Ans = get(tt);
			if(Ans==Inf32)continue;
			rep(k,3){
				Ans += rs[ii] - 1 - k;
			}
			ans[ii] = Ans;
		}
	}
	rep(_,q){
		printf("%d\n", ans[_]);
	}
}
0