Submission #1083143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083143		BLOBVISGOD	Election (BOI18_election)	C++17	100 / 100	296 ms	30020 KiB

election

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

struct segtree{
    struct node{
        int sm=0, L=0, R=0, A=0;
        node operator+(node b){
            return node{sm+b.sm,
                max(L,sm+b.L),
                max(b.R,b.sm+R),
                max(max(sm+b.A,A+b.sm),L+b.R)};
        }
    };

    int n;
    vector<node> seg;
    segtree(vi a){
        n = 1;
        while(n<sz(a)) 
            n*=2;
        seg.resize(n*2);
        rep(i,0,sz(a)) seg[i+n] = {a[i],max(0,a[i]),max(0,a[i]),max(0,a[i])};
        for(int i = n-1; i>0; --i) seg[i] = seg[i*2]+seg[i*2+1];
    }

    node query(int id, int l, int r, int ql, int qr){
        if (r <= ql or l >= qr) return {};
        else if (l >= ql and r <= qr) return seg[id];
        else{
            int mid = (l+r)/2;
            return query(id*2,l,mid,ql,qr)+query(id*2+1,mid,r,ql,qr);
        }
    }
};

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n; cin >> n;
    vi a(n);
    string s; cin >> s;
    rep(i,0,n){
        a[i] = (s[i]=='T'?1:-1);
    }

    segtree seg(a);

    int q; cin >> q;
    while(q--){
        int l,r; cin >> l >> r;
        l--;
        auto ret = seg.query(1,0,seg.n,l,r);
        cout << ret.A << '\n';
    }
}

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