Submission #646732

#	Time	Username	Problem	Language	Result	Execution time	Memory
646732		jasmin	Election (BOI18_election)	C++14	100 / 100	683 ms	89884 KiB

election

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

struct node{
    int free_left=0;
    int free_right=0;
    int left=0;
    int right=0;
    int both=0;
};
node zero={0, 0, 0, 0, 0};

struct segtree{
    vector<node> tree;

    segtree(int n, string& s){
        tree.resize(n*4);
        build(0, n, 0, s);
    }
    node build(int l, int r, int v, string& s){
        if(l+1==r){

            if(s[l]=='T'){
                tree[v].both=1;
            }
            else{
                tree[v].free_left=1;
                tree[v].free_right=1;
            }
            //cout << l << " " << r << " " << v << ": \n";
            //cout << tree[v].both << " " << tree[v].left << " " << tree[v].right << " " << tree[v].free_left << " " << tree[v].free_right << "\n";
            return tree[v];
        }
        int m=l+(r-l)/2;
        tree[v]=merge(build(l, m, v*2+1, s), build(m, r, v*2+2, s));
        //cout << l << " " << r << " " << v << ": \n";
        //cout << tree[v].both << " " << tree[v].left << " " << tree[v].right << " " << tree[v].free_left << " " << tree[v].free_right << "\n";
        return tree[v];
    }

    node merge(node a, node b){
        node ans;
        ans.free_left=a.free_left+b.free_left;
        ans.free_right=a.free_right+b.free_right;
        ans.left=a.left+b.left;
        ans.right=a.right+b.right;
        ans.both=a.both+b.both;

        int sright=0;
        int sleft=0;

        int x=min(a.right, b.free_left);
        sright=a.right-x;
        ans.right-=x; 
        ans.free_left-=x;

        x=min(a.both, b.free_left-x);
        ans.left+=x;
        ans.both-=x;
        ans.free_left-=x;

        int y=min(a.free_right, b.left);
        sleft=b.left-y;
        ans.left-=y;
        ans.free_right-=y;

        y=min(a.free_right-y, b.both);
        ans.right+=y;
        ans.both-=y;
        ans.free_right-=y;

        int k=min(sright, sleft);
        ans.right-=k;
        ans.left-=k;
        ans.both+=k;
        return ans;
    }

    node query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return zero;
        if(ql<=l && r<=qr) return tree[v];
        int m=l+(r-l)/2;
        return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    string votes;
    cin >> votes;
    segtree seg(n, votes);

    int q;
    cin >> q;
    for(int i=0; i<q; i++){
        int l, r;
        cin >> l >> r;

        node resp=seg.query(0, n, 0, l-1, r);
        int ans=resp.both+resp.left+resp.right;
        cout << ans << "\n";
    }
}

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