Submission #1264412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264412		altern23	Election (BOI18_election)	C++20	28 / 100	9 ms	1284 KiB

election

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 2e3;
const ll INF = 4e18;
const int MOD = 1e9 + 7;

ll ps[MAXN + 5][2];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		string S; cin >> S;
		S = '%' + S;
		
		for(int i = 1; i <= N; i++){
			ps[i][0] = ps[i - 1][0] + (S[i] == 'C');
			ps[i][1] = ps[i - 1][1] + (S[i] == 'T');
		}
		
		ll Q; cin >> Q;
		for(int i = 1; i <= Q; i++){
			ll l, r; cin >> l >> r;
			ll lf = 1, rg = ps[r][1] - ps[l - 1][1], ans = 0;
			for(;lf <= rg;){
				ll mid = (lf + rg) / 2;
				ll cnt = 0;
				for(int j = l; j <= r; j++){
					if(S[j] == 'T' && ps[j][0] - ps[l - 1][0] - (cnt + 1) >= 0 && ps[r][0] - ps[j - 1][0] - (mid - cnt) >= 0){
						cnt++;
					}
				}
				if(cnt >= mid){
					ans = mid;
					lf = mid + 1;
				}
				else rg = mid - 1;
			}
			
			cout << r - l + 1 - (ps[r][0] - ps[l - 1][0] + ans) << "\n";
		}
	}
}

/*

*/

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