Submission #584277

#	Time	Username	Problem	Language	Result	Execution time	Memory
584277		Arnch	Election (BOI18_election)	C++17	0 / 100	17 ms	340 KiB

election

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int ps[N], sf[N];
int nus[N], nuf[N];

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n; cin >>n;
	string s; cin >>s;

	int q; cin >>q;
	while(q--) {
		int l, r; cin >>l >>r; l--, r--;
		string t = "";
		for(int i = l; i <= r; i++) t.push_back(s[i]);
		int mn_l = 0, mn_r = Sz(t) - 1, sum = 0, nu = 0;
		for(int i = 0; i < Sz(t); i++) {
			if(t[i] == 'T') sum--, nu++;
			else sum++;
			ps[i] = sum;
			if(ps[i] <= ps[mn_l]) {
				mn_l = i;
			}
			nus[i] = nu;
		}
		sum = 0, nu = 0;
		for(int i = Sz(t) - 1; i >= 0; i--) {
			if(t[i] == 'T') sum--, nu++;
			else sum++;
			sf[i] = sum;
			if(sf[i] <= sf[mn_r]) {
				mn_r = i;
			}
			nuf[i] = nu;
		}
		t.clear();


		int ans = 0;
		if(mn_l < mn_r) {
			ans += min(nus[mn_l], -ps[mn_l]);
			ans += min(nuf[mn_r], -sf[mn_r]);
			cout<<ans <<endl;
			continue;
		}

		if(ps[mn_l] < 0 && mn_r > 0) {
			ans += min(nus[mn_r - 1], -ps[mn_l]);
			ps[mn_l] += ans;
		}
		if(sf[mn_r] < 0 && mn_l < Sz(t) - 1) {
			int cnt = min(nuf[mn_l + 1], -sf[mn_r]);
			sf[mn_r] += cnt;
			ans += cnt;
		}
		int val = min(ps[mn_l], sf[mn_r]);
		if(val < 0) ans += -val;
		cout<<ans <<endl;
	}

    return 0;
}

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