Submission #1152233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152233		thelegendary08	Election (BOI18_election)	C++17	100 / 100	783 ms	48548 KiB

election

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int mxn = 5e5 + 5;
struct node{
    int pre, suf, ans, tot;
};
node tree[mxn * 4];
int ps[mxn];
int ss[mxn];
int v[mxn];
node mrg(node a, node b){
    return {min(a.pre, a.tot + b.pre), min(b.suf, b.tot + a.suf), min(a.ans + b.tot, min(a.tot + b.ans, a.pre + b.suf)), a.tot + b.tot};
}
void build(int l, int r, int node = 1){
    if(l == r){
        tree[node].pre = min(0LL, v[l]);
        tree[node].suf = min(0LL, v[l]);
        tree[node].ans = 1e18;
        tree[node].tot = v[l];
    }
    else{
        int mid = (l + r)/2;
        build(l, mid, node * 2);
        build(mid+1, r, node*2+1);
        tree[node] = mrg(tree[node*2], tree[node*2+1]);
       // cout<<l<<' '<<r<<' '<<tree[node].ans<<'\n';
    }
}

node quer(int tl, int tr, int l, int r, int node = 1){
    if(l == tl && r == tr){
        return tree[node];
    }
    if(tl > r || tr < l)return {(int)1e18, (int)1e18, (int)1e18, 0LL};
    int mid = (tl + tr)/2;
    return mrg(quer(tl, mid, l, min(r, mid), node*2), quer(mid+1, tr, max(l, mid+1), r, node*2+1));

}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	in(n);
	string s;
	cin>>s;
	f0r(i,n){
		if(s[i]=='T')v[i] = -1;
		else v[i] = 1;
	}
	ps[0] = v[0];
	FOR(i, 1, n)ps[i] = ps[i-1] + v[i];
	ss[n-1] = v[n-1];
	for(int i = n-2; i>=0; i--)ss[i] = ss[i+1] + v[i];
	build(0, n-1);
	in(q);
	while(q--){
		in2(a,b);
		a--; b--;
		node cur = quer(0,n-1,a,b);
		//cout<<cur.pre<<' '<<cur.suf<<' '<<cur.ans<<' '<<cur.tot<<'\n';
        if(a != b)cout<<-quer(0, n-1, a,b).ans<<'\n';
        else cout<<(v[a] == -1)<<'\n';
	}
}

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