oj.uz

답안 #955688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955688 2024-03-31T10:27:33 Z MinaRagy06 Election (BOI18_election) C++17
0 / 100
 2 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	int nxt[n]{}, lst = n, sz[n]{}, cnt = 0;
	for (int i = n - 1; i >= 0; i--) {
		nxt[i] = lst;
		cnt += s[i] == 'T';
		if (i - 1 >= 0 && s[i - 1] != s[i]) {
			lst = i;
		}
		if (i - 1 < 0 || s[i - 1] == 'C') {
			sz[i] = cnt;
			cnt = 0;
		}
	}
	int prv[n]{}, prf[n + 1]{};
	lst = -1;
	for (int i = 0; i < n; i++) {
		prv[i] = lst;
		if (i + 1 < n && s[i + 1] != s[i]) {
			lst = i;
		}
		prf[i + 1] = prf[i] + (s[i] == 'C');
	}
	auto sum = [&] (int l, int r) {
		return prf[r + 1] - prf[l];
	};
	int q;
	cin >> q;
	int ans[q]{};
	for (int k = 0; k < q; k++) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		if (s[l] == 'T') {
			if (nxt[l] > r) {
				ans[k] = r - l + 1;
				continue;
			}
			ans[k] += nxt[l] - l;
			l = nxt[l];
		}
		if (s[r] == 'T') {
			ans[k] += r - prv[r];
			r = prv[r];
		}
		for (int i = l; i <= r; i++) {
			ans[k] += max(0, sz[i] - min(sum(l, i), sum(i, r)));
		}
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -