Submission #1132389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132389		Gray	Election (BOI18_election)	C++20	100 / 100	467 ms	66456 KiB

election

#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

const ll INF = 2e18;
const ll MOD = 998244353;

struct SegTree{
    struct node{
        ll pref, suff, sum, res;
    };
    vector<node> t;
    ll sz, rsz;
    SegTree(ll N){
        sz=N*4; rsz=N;
        t.resize(sz);
    }
    node merge(node l, node r){
        node nw;
        nw.pref = min({l.pref, l.sum+r.pref, 0ll});
        nw.suff = min({r.suff, r.sum+l.suff, 0ll});
        nw.sum = l.sum+r.sum;
        nw.res = min({l.sum+r.res, r.sum+l.res, l.pref+r.suff, 0ll});
        return nw;
    }
    void build(ll tl, ll tr, ll v, string &s){
        if (tl==tr){
            t[v].sum = {s[tl]=='C'?1:-1};
            t[v].pref=t[v].suff=t[v].res=min(0ll, t[v].sum);
        }else{
            ll tm = (tl+tr)/2;
            build(tl, tm, v*2, s);
            build(tm+1, tr, v*2+1, s);
            t[v] = merge(t[v*2], t[v*2+1]);
        }
    }
    node query(ll tl, ll tr, ll v, ll l, ll r){
        if (tl==l and tr==r){
            return t[v];
        }else if (l>r) return {0, 0, 0, 0};
        else{
            ll tm = (tl+tr)/2;
            return merge(query(tl, tm, v*2, l, min(r, tm)), query(tm+1, tr, v*2+1, max(l, tm+1), r));
        }
    }
    ll query(ll l, ll r){
        return abs(query(0, rsz-1, 1, l, r).res);
    }
    void build(string &s){
        build(0, rsz-1, 1, s);
    }
};

void solve(){
    ll n; cin >> n;
    string s; cin >> s;
    SegTree tr(n); tr.build(s);
    ll q; cin >> q;
    while (q--){
        ll l, r; cin >> l >> r; l--; r--;
        cout << tr.query(l, r) << ln;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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