Submission #1283879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283879		nikd	Election (BOI18_election)	C++20	100 / 100	163 ms	21432 KiB

election

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

struct node{
    int sm, lmax, rmax, sol;
    node operator+(node b){
        node res;
        res.sm = sm+b.sm;
        res.lmax = max(lmax, b.lmax+sm);
        res.rmax = max(b.rmax, rmax+b.sm);
        res.sol = max(max(lmax + b.rmax, sm+b.sol), sol+b.sm);
        return res;
    }
};

struct segtree{
    int n; vector<node> t;
    void build(vector<int> &a){
        t.resize(2*(n = a.size()));
        for(int i = 0; i<n; i++) t[i+n] = node{a[i], max(a[i], 0), max(a[i], 0), max(a[i], 0)};
        for(int i = n-1; i>0; i--) t[i] = t[i<<1] + t[i<<1|1];
    }
    int q(int l, int r){
        node lq{0, 0, 0, 0}, rq{0, 0, 0, 0};
        for(l+=n, r+=n; l<=r; l>>=1, r>>=1){
            if(l&1) lq = lq+t[l++];
            if(!(r&1)) rq = t[r--]+rq;
        }
        return (lq+rq).sol;
    }
};

int main(){
    iostream::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    string s; cin >> s;
    vector<int> vec(n);
    for(int i = 0; i<n; i++) vec[i] = (s[i] == 'C' ? -1 : 1);
    segtree seg;
    seg.build(vec);
    int q; cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        cout << seg.q(--l, --r) << '\n';
    }
}

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