Submission #385239

#	Time	Username	Problem	Language	Result	Execution time	Memory
385239		MODDI	Election (BOI18_election)	C++14	0 / 100	9 ms	364 KiB

election

#include <bits/stdc++.h>
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n;
string str;
int main(){
	cin>>n>>str;
	int lp[n][2], rp[n][2];
	memset(lp, 0, sizeof(lp));
	memset(rp, 0, sizeof(rp));
	for(int i = 0; i < n; i++){
		if(i == 0){
			lp[0][1] = (str[i] == 'C');
			lp[0][0] = (str[i] == 'T');
		}
		else{
			lp[i][1] = lp[i-1][1] + (str[i] == 'C');
			lp[i][0] = lp[i-1][0] + (str[i] == 'T');
		}
		//cout<<lp[i][0]<<" "<<lp[i][1]<<endl;
	}
	for(int i = str.size()-1; i >= 0; i--){
		if(i == str.size()-1){
			rp[i][1] = (str[i] == 'C');
			rp[i][0] = (str[i] == 'T');
		}
		else{
			rp[i][1] = rp[i+1][1] + (str[i] == 'C');
			rp[i][0] = rp[i+1][0] + (str[i] == 'T');
		}
	}
	int q;
	cin>>q;
	while(q--)
	{
		int a, b;
		cin>>a>>b;
		a--; b--;
		int removeC = 0, removeT = 0;
		if(a > 0)
			removeC = lp[a-1][1], removeT = lp[a-1][0];
			
		int lp_min = 1e9, rp_min = 1e9;
		for(int i = a; i<= b; i++){
			int curC = lp[i][1] - removeC, curT = lp[i][0] - removeT;
			int keep = curC - curT;
			
			lp_min = min(lp_min, keep);
		}
		removeC = 0;
		removeT = 0;
		if(b < n-1)
			removeC = rp[b+1][1], removeT = rp[b+1][0];
			
		for(int i = a; i<= b; i++){
			int curC = rp[i][1] - removeC, curT = rp[i][0] - removeT;
			//	cout<<curC<<" "<<curT<<" "<<removeC<<" "<<removeT<<endl;
			int keep = curC - curT;
			rp_min = min(rp_min, keep);
		}
		
		cout<<-min(rp_min,lp_min)<<endl;
	}
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:29:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   if(i == str.size()-1){
      |      ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18