Submission #951387

#	Time	Username	Problem	Language	Result	Execution time	Memory
951387		idiotcomputer	Election (BOI18_election)	C++11	0 / 100	1 ms	348 KiB

election

#include <bits/stdc++.h>
using namespace std;

string s;
const int mxN = 5e5;
int n;

struct node {
    int l, r, s, a;
};

node segtree[4*mxN+1];

void comb(node &a, node &b, node &c){
    c.a = max(a.l+b.r, max(a.s+b.a, a.a + b.s));
    c.l = max(a.l,a.s+b.l);
    c.r = max(a.r+b.s,b.r);
    c.s = a.s+b.s;
}

void build(int l = 0, int r = n-1, int idx = 0){
    if (l == r){
        if (s[l] == 'C'){
            segtree[idx].s = -1;
        } else {
            segtree[idx].s = 1;
        }
        segtree[idx].l = segtree[idx].s;
        segtree[idx].r = segtree[idx].s;
        segtree[idx].a = 0;
        if (segtree[idx].s > 0) segtree[idx].a = 1;
        return;
    }
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
    comb(segtree[2*idx+1],segtree[2*idx+2],segtree[idx]);
    segtree[idx].a = max(segtree[idx].a,0);
}

void query(int tl, int tr, node &res, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl){
        return;
    }
    if (l >= tl && r <= tr){
        comb(res,segtree[idx],res);
        return;
    }
    int m = (l+r)/2;
    query(tl,tr,res,l,m,2*idx+1);
    query(tl,tr,res,m+1,r,2*idx+2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int q;
    cin >> n >> s >> q;
    
    build();
    int l,r;
    node res;
    for (int i =0; i < q; i++){
        cin >> l >> r;
        l -= 1;
        r -= 1;
        res.l = -1e9;
        res.r = -1e9;
        res.s = 0;
        res.a = 0;
        query(l,r,res);
        cout << res.a << "\n";
    }
    
    
    return 0;
}

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