Submission #384175

#	Time	Username	Problem	Language	Result	Execution time	Memory
384175		sumit_kk10	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	28 ms	2736 KiB

ho_t2

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
int n, k;
string s;

void solve(){
	cin >> n >> k >> s;
	map<char, vector<int> > pos;
	
	for(int i = 0; i < s.size(); ++i)
		pos[s[i]].push_back(i);
	
	int pre_sum[pos['J'].size()] = {0}, pre_sum1[pos['O'].size()] = {0}, pre_sum2[pos['I'].size()] = {0};
	
	for(int i = 1; i < pos['J'].size(); ++i)
		pre_sum[i] = pre_sum[i - 1] + (pos['J'][i] - pos['J'][i - 1] - 1);

	for(int i = 1; i < pos['O'].size(); ++i)
		pre_sum1[i] = pre_sum1[i - 1] + (pos['O'][i] - pos['O'][i - 1] - 1);

	for(int i = 1; i < pos['I'].size(); ++i)
		pre_sum2[i] = pre_sum2[i - 1] + (pos['I'][i] - pos['I'][i - 1] - 1);

	int ans = INT_MAX;

	for(int i = 0; i < pos['J'].size(); ++i){
		int till = i + k - 1;
		if(till >= pos['J'].size()) 
			continue;
		int res;
		res = pre_sum[till] - pre_sum[i];
		int from = pos['J'][till] + 1;
		int low = 0, high = pos['O'].size() - 1, cur = -1;
		while(low <= high){
			int mid = (low + high) / 2;
			if(pos['O'][mid] >= from){
				cur = mid;
				high = mid - 1;
			}
			else
				low = mid + 1;
		}
		if(cur == -1) continue;
		if(cur + k - 1 >= pos['O'].size()) continue;
		res += pos['O'][cur] - from;
		res += pre_sum1[cur + k - 1] - pre_sum1[cur];
		int from1 = pos['O'][cur + k - 1] + 1;
		low = 0, high = pos['I'].size() - 1, cur = -1;
		while(low <= high){
			int mid = (low + high) / 2;
			if(pos['I'][mid] >= from1){
				cur = mid;
				high = mid - 1;
			}
			else
				low = mid + 1;
		}
		if(cur == -1) continue;
		if(cur + k - 1 >= pos['I'].size()) continue;
		res += pos['I'][cur] - from1;
		res += pre_sum2[cur + k - 1] - pre_sum2[cur];
		ans = min(ans, res); 
	}
	cout << (ans == INT_MAX ? -1 : ans) << "\n";
}

int main(){
    fast;
	int t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < s.size(); ++i)
      |                 ~~^~~~~~~~~~
ho_t2.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 1; i < pos['J'].size(); ++i)
      |                 ~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 1; i < pos['O'].size(); ++i)
      |                 ~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 1; i < pos['I'].size(); ++i)
      |                 ~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i = 0; i < pos['J'].size(); ++i){
      |                 ~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:32:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   if(till >= pos['J'].size())
      |      ~~~~~^~~~~~~~~~~~~~~~~~
ho_t2.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   if(cur + k - 1 >= pos['O'].size()) continue;
      |      ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
ho_t2.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if(cur + k - 1 >= pos['I'].size()) continue;
      |      ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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