제출 #951388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951388		idiotcomputer	Election (BOI18_election)	C++11	100 / 100	319 ms	28132 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 = max(0,segtree[idx].s);
        segtree[idx].r = max(0,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);
    //cout << l << "," << r << ": " << segtree[idx].l << " " << segtree[idx].r << " " << segtree[idx].s << " " << segtree[idx].a << '\n';
}

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 = 0;
        res.r = 0;
        res.s = 0;
        res.a = 0;
        query(l,r,res);
        cout << res.a << "\n";
    }
    
    
    return 0;
}

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