Submission #865475

#	Time	Username	Problem	Language	Result	Execution time	Memory
865475		farica	Election (BOI18_election)	C++14	100 / 100	1231 ms	28328 KiB

election

#include <bits/stdc++.h>
#define long long ll

using namespace std;

const int MAX_N=1e6;

struct Node {
    int sum, pref, suf, ans;
    Node operator+(Node b) {
		Node ret;
		ret.sum = sum + b.sum;
        ret.pref = max(pref, b.pref + sum);
        ret.suf = max(b.suf, suf + b.sum);
        ret.ans = max(max(ans + b.sum, b.ans + sum), pref + b.suf);
		return ret;
	}

};

string s;
Node seg[4*MAX_N];
int L,R;

void build(int node, int l, int r) {
    if(l==r) {
        if(s[l]=='T') seg[node].sum = seg[node].ans = seg[node].pref = seg[node].suf = 1;
        else {
            seg[node].sum = -1;
            seg[node].pref = seg[node].suf = seg[node].ans = 0;
        }
        return;
    }
    int m = (l+r)/2;
    build(2*node, l, m);
    build(2*node+1, m+1, r);
    seg[node] = seg[2*node] + seg[2*node+1];
}

Node check(int node, int l, int r) {
    if(l>R or r<L) return {0, 0, 0, 0};
    if(l>=L && r<=R) return seg[node];
    else return check(2*node, l, (l+r)/2) + check(2*node+1, (l+r)/2+1, r);
}

void solve() {
    int n;
    cin >> n;
    cin >> s;
    int q;
    cin >> q;
    build(1, 0, n-1);
    while(q--) {
        int l,r;
        cin >> l >> r;
        --l, --r;
        L=l, R=r;
        cout << check(1, 0, n-1).ans << endl;
    }
}

int main()
{
    int T=1;
    while(T--) solve();

    return 0;
}

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