Submission #762181

#	Time	Username	Problem	Language	Result	Execution time	Memory
762181		hqminhuwu	Election (BOI18_election)	C++17	0 / 100	2 ms	340 KiB

election

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N=2e5 + 5;
const ll oo = 1e9;
int n,a[N][2],i,t[4*N][2];
string s;
void build (int i, int l, int r){
    if (l == r){
        t[i][0] = a[l][0];
        t[i][1] = a[l][1];
        return;
    }
    int mid = (l + r)/2;
    build (i*2, l, mid);
    build (i*2 + 1, mid + 1, r);
    t[i][0] = min (t[i * 2][0], t[i * 2 + 1][0]);
    t[i][1] = min (t[i * 2][1], t[i * 2 + 1][1]);
}

int get (int k, int i, int l, int r, int u, int v){
    if (l > v || r < u)
        return oo;
    if (l >= u && r <= v)
        return t[i][k];
    int mid = (l + r)/2;
    return min (get(k, i * 2, l, mid, u , v), get (k,i * 2 + 1, mid + 1, r, u, v));
}
int q,l,r;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    cin >> s;
    forr (i,1,n){
        a[i][0] = a[i - 1][0];
        a[n - i + 1][1] = a[n - i + 2][1];
        if (s[i - 1] == 'C')
            a[i][0]++;
        else a[i][0]--;
        if (s[n - i] == 'C')
            a[n - i + 1][1]++;
        else a[n - i + 1][1]--;
    }
    build (1,1,n);
    cin >> q;
    while (q--){
        cin >> l >> r;
        cout << abs (min((get(0,1,1,n,l,r) - a[l - 1][0]),get(1,1,1,n,l,r) - a[r + 1][1])) << "\n";
    }
    return 0;
}
/*



*/

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