Submission #534187

#	Time	Username	Problem	Language	Result	Execution time	Memory
534187		Haruto810198	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	14 ms	5200 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const double eps = 1e-12;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

const int MAX = 200010;

int n, k;
int pref[4][MAX]; // J = 1, O = 2, I = 3

int jl, jr, il, ir;
int res = INF;

inline int query(int ql, int qr, char qc){
	if(qc == 'J') return pref[1][qr] - pref[1][ql-1];
	if(qc == 'O') return pref[2][qr] - pref[2][ql-1];
	return pref[3][qr] - pref[3][ql-1];
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;
	FOR(i, 1, n, 1){
		char owo;
		cin>>owo;
		FOR(j, 1, 3, 1) pref[j][i] = pref[j][i-1];
		if(owo == 'J') pref[1][i]++;
		if(owo == 'O') pref[2][i]++;
		if(owo == 'I') pref[3][i]++;
	}
	FOR(j, 1, 3, 1) pref[j][n+1] = INF;
	
	//cerr<<"ok"<<endl;

	jl = 1, jr = 0, il = 0, ir = 0;
	while(jl <= n){
		// move [jl, jr]
		while(jr <= n and query(jl, jr, 'J') < k) jr++;
		il = max(il, jr + 1);
		while(ir <= n and query(il, ir, 'I') < k) ir++;
		if(ir > n) break;
		
		//cerr<<"? "<<'['<<jl<<", "<<jr<<"] ["<<il<<", "<<ir<<"] "<<endl;

		// move [il, ir] until [jr+1, ir-1] is ok
		while(query(jr+1, il-1, 'O') < k){
			il++;
			while(ir <= n and query(il, ir, 'I') < k) ir++;
			if(ir > n) break;

			//cerr<<". "<<'['<<jl<<", "<<jr<<"] ["<<il<<", "<<ir<<"] "<<endl;
		}
		
		if(ir > n) break;

		// update res
		res = min(res, ir - jl + 1 - 3*k);
		//cerr<<"! "<<'['<<jl<<", "<<jr<<"] ["<<il<<", "<<ir<<"] "<<endl;
		jl++;
	}

	if(res < INF) cout<<res<<'\n';
	else cout<<-1<<'\n';
	
	return 0;

}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87