Submission #957275

#	Time	Username	Problem	Language	Result	Execution time	Memory
957275		Icelast	Election (BOI18_election)	C++17	100 / 100	499 ms	44620 KiB

election

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 5*1e5+5, INF = 4e18+9;
ll n, Q;
string s;
void inp(){
    cin >> n;
    cin >> s;
    s = ' ' + s;
    cin >> Q;
}
struct Node{
    ll L, R, S, res;
};
ll N;
Node T[4*maxn];
Node merg(Node a, Node b){
    Node res;
    res.S = a.S+b.S;
    res.L = max(a.L, a.S+b.L);
    res.R = max(b.R, a.R+b.S);
    res.res = max(max(a.S+b.res, a.res+b.S), a.L+b.R);
    return res;
}
void build_segtree(){
    N = 1;
    while(N < n) N*=2;
    for(int i = 1; i <= n; i++){
        if(s[i] == 'C'){
            T[i+N-1] = {0, 0, -1, 0};
        }else{
            T[i+N-1] = {1, 1, 1, 1};
        }
    }
    for(int i = n+1; i <= N; i++){
        T[i+N-1] = {0, 0, 0, 0};
    }
    for(int i = N-1; i >= 1; i--){
        T[i] = merg(T[i*2], T[i*2+1]);
    }
}
Node get(int node, int low, int high, int l, int r){
    if(low > r || l > high) return {0, 0, 0, 0};
    if(low >= l && r >= high) return T[node];
    int mid = (low+high)/2;
    return merg(get(node*2, low, mid, l, r), get(node*2+1, mid+1, high, l, r));
}
void solve(){
    build_segtree();
    int l, r;
    for(int i = 1; i <= Q; i++){
        cin >> l >> r;
        cout << get(1, 1, N, l, r).res << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    inp();
    solve();
}

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