Submission #1082633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082633		BLOBVISGOD	Election (BOI18_election)	C++17	0 / 100	2 ms	600 KiB

election

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

struct segtree{
    struct node{
        int sum=0, minpref=0, id=0;
        node operator+(node b){
            node ans;
            ans.sum = sum + b.sum;
            if (sum + b.minpref < minpref){
                ans.minpref = sum + b.minpref;
                ans.id = b.id;
            }else{
                ans.minpref = minpref;
                ans.id = id;
            }
            return ans;
        }
    };

    int n;
    vector<node> a;

    segtree(vi b){
        n = 1;
        while(n < sz(b)) n*=2;
        a.resize(n*2);

        rep(i,0,sz(b)){
            if (b[i]<=0) a[n+i] = {b[i],b[i],i};
            else a[n+i] = {b[i],0,i-1};
        }

        for (int i = n-1; i>0; --i) a[i] = a[i*2]+a[i*2+1];
    }

    node query(int id, int l, int r, int ql, int qr){
        if (l >= ql and r <= qr) return a[id];
        else if (r <= ql or l >= qr) return {};
        else{
            int mid = (l+r)/2;
            return query(id*2,l,mid,ql,qr)+query(id*2+1,mid,r,ql,qr);
        }
    }
    node get(int l, int r){
        return query(1,0,n,l,r);
    }
};

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,q; cin >> n;
    string s; cin >> s;
    vi a(n),b;
    rep(i,0,n) a[i] = (s[i]=='C')?1:-1;
    b = a;
    reverse(all(b)); // i -> n-1-i

    segtree LtoR(a), RtoL(b);

    cin >> q;
    while(q--){
        int l,r; cin >> l >> r; // [l,r]
        l--,r--;
        // LtoR : l r+1
        // RtoL : n-1-r n-l
        auto ansL = LtoR.get(l,r+1), ansR = RtoL.get(n-1-r,n-l);
        int L = n-1-ansR.id, R = ansL.id;
        if (L > R) cout << max(0,-ansR.minpref)+max(0,-ansL.minpref) << '\n';
        else{
            auto ansL2 = LtoR.get(l,L);
            cout << max(0,-ansL2.minpref)+max(0,-ansR.minpref) << '\n';
        }
    }
    
}

/*

1 1
CCCTTTTTTCC
3
1 11
4 9
1 6


*/ 

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