제출 #1098564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098564		Nurislam	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	0 ms	348 KiB

ho_t2

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>  
using namespace std;
//using namespace __gnu_pbds;z
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
//#define ordst tree<pair<int,int>,  null_type,  less<pair<int,int>>,  rb_tree_tag ,  tree_order_statistics_node_update >
//#define double long double 
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

const int N = (1<<18) +1, inf = 1e18+200;
//int mod = 998244353;
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
void solve(){
	map<char,int> mp;
	mp['J'] = 0;
	mp['O'] = 1;
	mp['I'] = 2;
	vector<int> a;a.pb(-1);
	
	auto conv = [&](string s)->void{
		for(auto &i:s)a.pb(mp[i]);
	};
	
	int n, k;
	cin >> n >> k;
	string s;cin >> s;conv(s);
	vector<vector<int>> pref(n+1, vector<int> (3, 0));
	for(auto &i:pref[0])i = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 3; j++)
			pref[i][j] = pref[i-1][j];
		pref[i][a[i]]++;
	}
	auto get = [&](int l, int r, int t) -> int{
		return pref[r][t] - pref[l-1][t];
	};
	
	auto ch = [&]()->bool{
		vector<int> v;
		for(int i = 1; i <= n; i++)if(a[i] == 1)v.pb(i);
		
		for(int i = 0; i < (int)v.size(); i++){
			if(i+k-1 == (int)v.size())break;
			int l = v[i], r = v[i+k-1];
			if(get(1, l, 0) >= k && get(r, n, 2) >= k)return true;
		}
		return false;
	};
	if(!ch()){cout << "-1\n";return;}
	
	vector<int> v;
	for(int i = 1; i <= n; i++)if(a[i] == 1)v.pb(i);
	
	int ans = inf;
	int il = 0, ir = k-1;
	int last = inf;
	while(ir < (int)v.size()){
		//cout << il << ' ' << ir << '\n';
		int l = v[il]-1, r = v[ir]+1;
		int rek = ir-il+1;
		int tol = l;
		for(int i = 20; i >= 0; i--){
			int nwl = max(1ll, tol-(1<<i));
			if(get(nwl, l, 0) >= rek)continue;
			tol = nwl;
		}
		tol--;
		int tor = r;
		for(int i = 20; i >= 0; i--){
			int nwr = min(n, tor+(1<<i));
			if(get(r, nwr, 2) >= rek)continue;
			tor = nwr;
		}
		tor++;
		int cur = tor-tol+1 - rek*3;
		chmin(ans, cur);
		
		if(ir-il+1 == k)ir++;
		else if(ir+1 == (int)v.size())il++;
		else if(chmin(last, cur))ir++;
		else il++;
		//cout << il << ' ' << ir << '\n';
	}
	
	cout << ans << '\n';
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}

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