Submission #376632

#	Time	Username	Problem	Language	Result	Execution time	Memory
376632		couplefire	Election (BOI18_election)	C++17	0 / 100	15 ms	8684 KiB

election

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

struct Seg{
    int tree[2*MAXN] = {0};
    Seg(){}
    void upd(int pos, int val, int tl = 0, int tr = MAXN-1, int v = 1){
        if(tl > pos || tr < pos) return;
        if(tl == tr){
            tree[v] = val;
            return;
        }
        int mid = (tl+tr)/2;
        upd(pos, val, tl, mid, v*2);
        upd(pos, val, mid+1, tr, v*2+1);
        tree[v] = max(tree[v*2], tree[v*2+1]);
    }
    int query(int l, int r, int tl = 0, int tr = MAXN-1, int v = 1){
        if(tl > r || tr < l) return -MAXN;
        if(l <= tl && tr <= r) return tree[v];
        int tm = (tl+tr)/2;
        return max(query(l, r, tl, tm, v*2), query(l, r, tm+1, tr, v*2+1));
    }
} leftseg, rightseg;

int n, q;
int arr[MAXN];
int leftval[MAXN], rightval[MAXN];
string s;

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;
    for(int i = 0; i<n; i++){
        arr[i+1] = (s[i] == 'C')?-1:1;
    }
    for(int i = 1; i<=n; i++) leftval[i] = arr[i]+leftval[i-1];
    for(int i = n; i>=1; i--) rightval[i] = arr[i]+rightval[i+1];
    for(int i = 1; i<=n; i++) leftseg.upd(i, leftval[i]), rightseg.upd(i, rightval[i]);
    cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        cout << max(0, max(leftseg.query(l, r)-leftval[l-1], rightseg.query(l, r)-rightval[r+1])) << endl;
    }
}

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