Submission #313423

#	Time	Username	Problem	Language	Result	Execution time	Memory
313423		Vince729	Election (BOI18_election)	C++11	100 / 100	621 ms	20276 KiB

election

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 500002;
const int MOD = 1000000007;

struct node {
    int lmx, rmx, sum, ans;

    node operator+(node o) {
        node ret;
        ret.lmx = max(lmx, o.lmx+sum);
        ret.rmx = max(rmx+o.sum, o.rmx);
        ret.sum = sum+o.sum;
        ret.ans = max(max(ans+o.sum, sum+o.ans), lmx+o.rmx);
        return ret;
    }
};

int n, q;
bool votes[MAXN];
node st[1<<20];

void build(int l=1, int r=n, int x=1) {
    if (l == r) {
        if (votes[l]) st[x] = {1, 1, 1, 1};
        else st[x] = {0, 0, -1, 0};
    } else {
        int mid = (l+r)/2;
        build(l, mid, 2*x);
        build(mid+1, r, 2*x+1);
        st[x] = st[2*x]+st[2*x+1];
    }
}

node qry(int a, int b, int l=1, int r=n, int x=1) {
    if (a <= l && b >= r) return st[x];
    node ret = {0, 0, 0, 0};
    int mid = (l+r)/2;
    if (a <= mid) ret = ret+qry(a, b, l, mid, 2*x);
    if (b > mid) ret = ret+qry(a, b, mid+1, r, 2*x+1);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c; cin >> c;
        votes[i] = c == 'T';
    }
    build();

    cin >> q;
    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;
        cout << qry(a, b).ans << '\n';
    }
}

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