Submission #1034074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034074		Andrey	Election (BOI18_election)	C++14	100 / 100	340 ms	44312 KiB

election

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

vector<int> haha(500001);
vector<int> brl(2000001);
vector<int> brr(2000001);
vector<int> wow(2000001);
vector<int> sb(2000001);

pair<pair<int,int>,pair<int,int>> merge(pair<pair<int,int>,pair<int,int>> a, pair<pair<int,int>,pair<int,int>> b) {
    pair<int,int> c = a.first,d = a.second,e = b.first,f = b.second;
    int sb = c.second+e.second;
    int br1 = d.first+max(0,f.first-(c.second+d.first));
    int br2 = f.second+max(0,d.second-(e.second+f.second));
    int x = max(0,e.first-f.second-(c.second+d.first));
    int y = max(0,c.first-d.first-(e.second+f.second+x));
    return {{d.first+f.second+x+y,sb},{br1,br2}};
}

void build(int l, int r, int x) {
    if(l == r) {
        sb[x] = haha[l];
        if(haha[l] == -1) {
            brl[x] = 1;
            brr[x] = 1;
            wow[x] = 1;
        }
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    pair<pair<int,int>,pair<int,int>> c = merge({{wow[x*2],sb[x*2]},{brl[x*2],brr[x*2]}},{{wow[x*2+1],sb[x*2+1]},{brl[x*2+1],brr[x*2+1]}});
    sb[x] = c.first.second;
    brl[x] = c.second.first;
    brr[x] = c.second.second;
    wow[x] = c.first.first;
}

pair<pair<int,int>,pair<int,int>> calc(int l, int r, int ql, int qr, int x) {
    if(l == ql && r == qr) {
        return {{wow[x],sb[x]},{brl[x],brr[x]}};
    }
    int mid = (l+r)/2;
    if(qr <= mid) {
        return calc(l,mid,ql,qr,x*2);
    }
    else if(ql > mid) {
        return calc(mid+1,r,ql,qr,x*2+1);
    }
    else {
        return merge(calc(l,mid,ql,mid,x*2),calc(mid+1,r,mid+1,qr,x*2+1));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,q,l,r;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        char a;
        cin >> a;
        if(a == 'C') {
            haha[i] = 1;
        }
        else {
            haha[i] = -1;
        }
    }
    build(1,n,1);
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> l >> r;
        cout << calc(1,n,l,r,1).first.first << "\n";
    }
    return 0;
}

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