結果

問題 No.3244 Range Multiple of 8 Query
ユーザー 沙耶花
提出日時 2025-08-22 21:54:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,267 bytes
コンパイル時間 4,268 ms
コンパイル使用メモリ 260,692 KB
実行使用メモリ 92,736 KB
最終ジャッジ日時 2025-08-22 21:55:25
合計ジャッジ時間 28,296 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23 TLE * 1 -- * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:81:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   81 |                 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>;
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;
}
vector<vector<int>> li;
int get(array<vector<int>, 9> res){
	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 -= tt[j];
		}
		ans = min(ans,cur);
	}
	return ans;
}

int main(){
	rep(i,9){
		Nul[i] = vector<int>();
	}
	
	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);
	}
	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 = e();
	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