Submission #713599

#	Time	Username	Problem	Language	Result	Execution time	Memory
713599		JJAnawat	Election (BOI18_election)	C++17	100 / 100	500 ms	28064 KiB

election

#include<bits/stdc++.h>

using namespace std;

struct node{
    int l,r,s,ans;

    node(int ll=0,int rr=0,int ss=0,int aa=0){
        l=ll;
        r=rr;
        s=ss;
        ans=aa;
    }
};

node seg[1<<20];
string ss;

node mer(node ln,node rn){
    node res;
    res.l=max(ln.l,ln.s+rn.l);
    res.r=max(rn.r,rn.s+ln.r);
    res.s=ln.s+rn.s;
    res.ans=max({ln.l+rn.r,ln.ans+rn.s,ln.s+rn.ans});
    return res;
}

void build(int l,int r,int i){
    if(l==r){
        if(ss[l]=='T')
            seg[i]=node(1,1,1,1);
        else
            seg[i]=node(0,0,-1,0);
        return;
    }
    int m=(l+r)/2;
    build(l,m,2*i);
    build(m+1,r,2*i+1);
    seg[i]=mer(seg[2*i],seg[2*i+1]);
}

node qr(int l,int r,int i,int x,int y){
    if(l>y||r<x)
        return node();
    if(l>=x&&r<=y)
        return seg[i];
    int m=(l+r)/2;
    return mer(qr(l,m,2*i,x,y),qr(m+1,r,2*i+1,x,y));
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    cin >> ss;
    ss=" "+ss;
    build(1,n,1);
    int q;
    cin >> q;
    int l,r;
    while(q--){
        cin >> l >> r;
        cout << qr(1,n,1,l,r).ans << "\n";
    }
}

Compilation message (stderr)

election.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      | ^~~~

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