Submission #679272

#	Time	Username	Problem	Language	Result	Execution time	Memory
679272		gyandevrey6	Election (BOI18_election)	C++17	100 / 100	992 ms	20284 KiB

election

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 500010;
struct node {
    int mnl, mnr, mns;
} seg[N*4];

string s;
int pre[N], suf[N];
int n;

inline node merge(const node& x,const node& y)
{
    node ans;
    ans.mnl = min(x.mnl, y.mnl);
    ans.mnr = min(x.mnr, y.mnr);
    ans.mns = min({x.mns, y.mns, x.mnl + y.mnr});
    return ans;
}

void build(int i, int b, int e)
{
    if (e-b == 1) {
        seg[i].mnl = pre[b];
        seg[i].mnr = suf[b];
        seg[i].mns = seg[i].mnl + seg[i].mnr;
        return;
    }
    build(2*i+1, b, (b+e)/2);
    build(2*i+2, (b+e)/2, e);
    seg[i] = merge(seg[2*i+1], seg[2*i+2]);
}

node get(int l, int r, int i, int b, int e)
{
    if (l <= b && e <= r)
        return seg[i];
    int mid = (b+e)/2;
    if (l < mid && mid < r) {
        return merge(get(l, r, 2*i+1, b, mid),
                     get(l, r, 2*i+2, mid, e));
    } else if (l < mid) {
        return get(l, r, 2*i+1, b, mid);
    } else {
        return get(l, r, 2*i+2, mid, e);
    }
}

int main()
{
    cin.tie(0) -> sync_with_stdio(false);
    int q;
    cin >> n;
    cin >> s;
    Loop (i,0,n)
        pre[i+1] = pre[i] + (s[i] == 'C'? 1: -1);
    LoopR (i,0,n)
        suf[i] = suf[i+1] + (s[i] == 'C'? 1: -1);
    build(0, 0, n+1);
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        auto ans = get(l, r+1, 0, 0, n+1);
        cout << -(ans.mns - pre[l] - suf[r]) << endl;
    }
}

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