Submission #926181

#	Time	Username	Problem	Language	Result	Execution time	Memory
926181		dosts	Election (BOI18_election)	C++17	0 / 100	2 ms	600 KiB

election

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define ordered_set tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>
const int inf = 2e18;

struct ST {
    struct Node {
        int wsuf,wpref,sm;
    };
    int n;
    string s;
    vector<Node> t;
    Node merge(Node a,Node b){
        Node ret;
        ret.wsuf = min(b.wsuf,b.sm+a.wsuf);
        ret.wpref = min(a.wpref,a.sm+b.wpref);
        ret.sm = a.sm+b.sm;
        return ret;
    }
    void build(int node,int l,int r) {
        if (l == r) {
            int c = s[l-1] == 'T'?-1:1;
            t[node] = {c,c,c};
            return;
        }        
        int m = (l+r) >> 1;
        build(2*node,l,m);
        build(2*node+1,m+1,r);
        t[node] = merge(t[2*node],t[2*node+1]);
        return;
    }
    ST(int nn,string ss) {
        n = nn;
        s = ss;
        t.resize(4*n+1);
        build(1,1,n);
    }
    Node id = {0,0,0};
    Node query(int node,int l,int r,int L,int R) {
        if (l > R || r < L) return id;
        if (l >= L && r <= R) return t[node];
        int m = (l+r) >> 1;
        return merge(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
    }
};
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    ST st(n,s);
    int q;
    cin >> q;
    while (q--) {
        int l,r;
        cin >> l >> r;
        cout << max(0ll,-min(st.query(1,1,n,l,r).wpref,st.query(1,1,n,l,r).wsuf)) << '\n';
    }
}         
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

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