Submission #883117

#	Time	Username	Problem	Language	Result	Execution time	Memory
883117		phoenix0423	Election (BOI18_election)	C++17	100 / 100	388 ms	28128 KiB

election

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 0, n + 1)
#define SZ(x) (int)(x).size()
#define pb push_back
#define pf push_front
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
// #define int long long
const int INF = 1e9;
const int maxn = 3e5 + 5;
int n, q;
string s;
struct node{
	int mxl, mxr, sum, ans;
	node operator + (node b){
		node ret;
		ret.mxl = max(mxl, b.mxl + sum);
		ret.mxr = max(mxr + b.sum, b.mxr);
		ret.sum = sum + b.sum;
		ret.ans = max(max(sum + b.ans, ans + b.sum), mxl + b.mxr);
		return ret;
	}
} st[maxn * 4];

void build(int v = 1, int l = 0, int r = n - 1){
	if(l == r){
		if(s[l] == 'T') st[v] = {1, 1, 1, 1};
		else st[v] = {0, 0, -1, 0};
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m + 1, r);
	st[v] = st[v * 2] + st[v * 2 + 1];
}
node qry(int l, int r, int v = 1, int L = 0, int R = n - 1){
	if(l > R || r < L) return {0, 0, 0, 0};
	if(l <= L && r >= R) return st[v];
	int m = (L + R) / 2;
	return qry(l, r, v * 2, L, m) + qry(l, r, v * 2 + 1, m + 1, R);
}
int main(void){
	fastio;
	cin>>n>>s>>q;
	build();
	for(int i = 0; i < q; i++){
		int l, r;
		cin>>l>>r;
		l--, r--;
		cout<<qry(l, r).ans<<"\n";
	}

}

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