Submission #598256

#	Time	Username	Problem	Language	Result	Execution time	Memory
598256		AlesL0	Election (BOI18_election)	C++17	0 / 100	2 ms	468 KiB

election

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segtree {
    ll sum, left, right;
};

vector <segtree> T;
ll k = 1;
vector <ll> sol;

const ll ZERO = 0;

void build(vector <int> a){
    ll n = a.size();
    while (k < n)k *= 2;
    T.resize(2*k);
    for (int i = 0; i < n; i++)T[i+k] = {a[i], max(a[i], 0), max(a[i], 0)};
    for (int i = k; i < n; i++)T[i+k] = {0, 0, 0};
    for (int i = k-1; i; i--)T[i] = {T[2*i].sum+T[2*i+1].sum, max(T[2*i].sum+T[2*i+1].left, T[2*i].left), max(T[2*i].right+T[2*i+1].sum, T[2*i+1].right)};
}

void range_query(ll i, ll x, ll y, ll l, ll r){
    if (l >= x && r <= y){sol.push_back(i); return;}
    if (l >= y || r <= x)return;
    range_query(2*i, x, y, l, (l+r)>>1); range_query(2*i+1, x, y, (l+r)>>1, r);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n; cin >> n;
    string s; cin >> s;
    vector <int> a(n, 1);
    for (int i = 0; i < n; i++)if (s[i] == 'C')a[i] = -1;
    build(a);
    cerr << endl << endl;;
    ll q; cin >> q;
    while (q--){
        ll l, r; cin >> l >> r;
        l--; r--;
        range_query(1, l, r+1, 0, k);
        ll sum = 0;
        r = 0;
        for (auto i : sol){
            r = max(r, sum+T[i].left);
            sum += T[i].sum;
        }
        sum = 0;
        for (int j = sol.size()-1; j >= 0; j--){
            ll i = sol[j];
            r = max(r, sum+T[i].right);
            sum += T[i].sum;
        }
        cout << r << "\n";
        sol.clear();
    }
}

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