제출 #1290202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290202		Jawad_Akbar_JJ	Election (BOI18_election)	C++20	100 / 100	336 ms	20372 KiB

election

#include <iostream>

using namespace std;
string s;
int n, q;

struct node{
	int ans = 0, sum = 0, mxPre = 0, mxSuf = 0;

	node operator*(node b){
		node res;
		res.sum = sum + b.sum;
		res.mxPre = max(mxPre, sum + b.mxPre);
		res.mxSuf = max(b.mxSuf, b.sum + mxSuf);

		res.ans = max(max(ans + b.sum, sum + b.ans), mxPre + b.mxSuf);
		return res;
	}
} seg[1<<20], nodeAns, dummy;

void build(int cur = 1, int st = 1, int en = n + 1){
	if (en - st == 1){
		if (s[st - 1] == 'T')
			seg[cur].ans = seg[cur].sum = seg[cur].mxPre = seg[cur].mxSuf = 1;
		else
			seg[cur].sum = -1;
		return;
	}

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	build(lc, st, mid);
	build(rc, mid, en);

	seg[cur] = seg[lc] * seg[rc];
}

void get(int l, int r, int cur = 1, int st = 1, int en = n + 1){
	if (l >= en or r <= st)
		return;
	if (l <= st and r >= en){
		nodeAns = nodeAns * seg[cur];
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	get(l, r, lc, st, mid);
	get(l, r, rc, mid, en);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n>>s>>q;

	build();

	for (int i=1, l, r;i<=q;i++){
		cin>>l>>r;

		nodeAns = dummy;
		get(l, r + 1);
		cout<<nodeAns.ans<<'\n';
	}
}

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