Submission #1281476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281476		dora_kyu	Election (BOI18_election)	C++20	0 / 100	1 ms	332 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define st first
#define nd second
#define endl "\n"
const int maxn = 5e5 + 5;
int pre[maxn], suf[maxn];
const int inf = 1e9 + 5;
string s;
int n, q;

pair<int,int> nod[maxn << 4];

void build(int id, int l, int r)
{
    if( l == r )
    {
        nod[id] = {pre[l], suf[l]}; return;
    }
    int m = l + r >> 1;
    build(id << 1, l , m);
    build(id << 1 | 1, m + 1, r);
    nod[id] = { min(nod[id << 1].st , nod[id << 1 | 1].st), min(nod[id << 1].nd , nod[id << 1 | 1].nd) };
}

pair<int,int> get(int id, int l, int r, int u, int v)
{
    if(l > v || r < u) return {inf,inf};
    if(l >= u && r <= v) return nod[id];
    int m = l + r >> 1;
    pair<int,int> p1 = get(id << 1, l , m , u , v);
    pair<int,int> p2 = get(id << 1 | 1, m + 1 , r, u , v);
    return { min(p1.st, p2.st), min(p1.nd, p2.nd) };
}

signed main()
{
    cin.tie(nullptr) -> ios_base::sync_with_stdio(0);
    cin >> n >> s;
    s = " " + s;
    for(int i = 1; i <= n;++i)
    {
        pre[i] = pre[i-1] + (s[i] == 'T' ? -1 : 1);
        suf[n - i + 1] = suf[n - i + 2] + (s[n-i+1] == 'T' ? -1 : 1);
    }
    build(1,1,n);
    cin >> q;

    for(int i = 1; i <= q; ++i)
    {
        int l, r; cin >> l >> r;
        pair<int,int> R = get(1,1,n,l,r);
        cout << abs( min( min(0,R.st - pre[l-1]), min(0, R.nd - suf[r + 1]) ) ) << endl;
    }

}

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