Submission #1232903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232903		Adnanboi	Election (BOI18_election)	C++20	0 / 100	46 ms	320 KiB

election

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

//ubit cu se

void solve() {
	int n;
	cin>>n;
	string s;
	cin>>s;
	vector<int> pre(n + 1), suf(n + 2), cSum(n + 1), tSum(n + 1);
	for(int i = 0; i < n; i++){
		cSum[i + 1] = cSum[i] + (s[i] == 'C');
		tSum[i + 1] = tSum[i] + (s[i] == 'T');
		pre[i + 1] = cSum[i + 1] - tSum[i + 1];
	}
	for(int i = n - 1; i >= 0; i--){
		suf[i + 1] = suf[i + 2] + (s[i] == 'C') - (s[i] == 'T');
	}

	vector<int> bad_pre(n + 1, 0), bad_suf(n + 2, 0);
	for(int i = 1; i <= n; i++) bad_pre[i] = min(bad_pre[i - 1], pre[i]);
	for(int i = n; i >= 1; i--) bad_suf[i] = min(bad_suf[i + 1], suf[i]);
	int q;
	cin>>q;
	while (q--) {
		int l, r;
		cin>>l>>r;
		int totalC = cSum[r] - cSum[l - 1];
		int totalT = tSum[r] - tSum[l - 1];
		int low = 0, high = totalT, ans = totalT;
		while(low <= high){
			int mid = (low + high) / 2;
			int c = 0, t = 0;
			vector<int> del;
			for(int i = l - 1; i < r && t < mid; i++){
				if(s[i] == 'T'){
					del.push_back(i);
					t++;
				}
			}
			vector<bool> skip(n, false);
			for (int x : del) skip[x] = true;
			bool valid = true;
			c = 0, t = 0;
			for(int i = l - 1; i < r; i++){
				if(skip[i]) continue;
				if(s[i] == 'C') c++;
				else t++;
				if(c < t){
					valid = false;
					break;
				}
			}
			c = 0, t = 0;
			for(int i = r - 1; i >= l - 1 && valid; i--){
				if(skip[i]) continue;
				if(s[i] == 'C') c++;
				else t++;
				if(c < t){
					valid = false;
					break;
				}
			}
			if(valid){
				ans = mid;
				high = mid - 1;
			} 
			else{
				low = mid + 1;
			}
		}
		cout<<ans<<'\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

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