Submission #1107175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107175		farica	Election (BOI18_election)	C++14	100 / 100	1216 ms	52724 KiB

election

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

using namespace std;

const int MAX_N = 5e5;
const int MOD = 1e9 + 7;
const int INF = 1e9;

struct Node {
    int L, R, A, S;
};

string s;

Node segm[4*MAX_N];

Node comb(Node a, Node b) {
    Node c;
    c.S = a.S + b.S;
    c.L = max(a.L, a.S + b.L);
    c.R = max(b.R, b.S + a.R);
    c.A = max(max(a.S + b.A, b.S + a.A), a.L + b.R);
    return c;
}

void build(int pos, int l, int r) {
    if(l==r) {
        if(s[l] == 'C') {
            segm[pos].S = -1;
            segm[pos].L = segm[pos].R = segm[pos].A = 0;
        } else {
            segm[pos].S = segm[pos].R = segm[pos].L = segm[pos].A = 1;
        }
        return;
    }
    int m = (l+r)/2;
    build(2*pos+1, l, m);
    build(2*pos+2, m+1, r);
    segm[pos] = comb(segm[2*pos+1], segm[2*pos+2]);
}

Node query(int pos, int l, int r, int L, int R) {
    if(l > R or r < L) {
        Node tmp;
        tmp.A = tmp.L = tmp.R = tmp.S = 0;
        return tmp;
    } else if(l >= L && r <= R) return segm[pos];
    int m = (l+r)/2;
    return comb(query(2*pos+1, l, m, L, R), query(2*pos+2, m+1, r, L, R));
}

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

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1;
    while(t--) solve();

    return 0;
}

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