Submission #80350

#	Time	Username	Problem	Language	Result	Execution time	Memory
80350		igzi	Election (BOI18_election)	C++17	100 / 100	1488 ms	105648 KiB

election

#include <bits/stdc++.h>
#define maxN 500005

using namespace std;

string s;
int n,q,x,y;
struct segment{
int a,l,d,x;
};
segment seg[4*maxN];

void build(int n,int l,int d){
if(l==d){
    if(s[l]=='T'){
        seg[n].a=seg[n].l=seg[n].d=1;
        seg[n].x=-1;
    }
    else{
        seg[n].a=seg[n].l=seg[n].d=0;
        seg[n].x=1;
    }
}
else{
    int m=(l+d)/2;
    build(2*n,l,m);
    build(2*n+1,m+1,d);
    seg[n].l=max(seg[2*n].l,seg[2*n+1].l-seg[2*n].x);
    seg[n].d=max(seg[2*n+1].d,seg[2*n].d-seg[2*n+1].x);
    seg[n].x=seg[2*n].x+seg[2*n+1].x;
    seg[n].a=max(max(seg[2*n].a-seg[2*n+1].x,seg[2*n+1].a-seg[2*n].x),seg[2*n].l+seg[2*n+1].d);
}
}

segment query(int n,int l,int d,int x,int y){
if(l>=x && d<=y) return seg[n];
int m=(l+d)/2;
segment a,b,ans;
a.a=a.l=a.d=a.x=b.a=b.l=b.d=b.x=0;
if(m>=x) a=query(2*n,l,m,x,y);
if(y>=m+1) b=query(2*n+1,m+1,d,x,y);
ans.x=a.x+b.x;
ans.l=max(a.l,b.l-a.x);
ans.d=max(b.d,a.d-b.x);
ans.a=max(max(a.a-b.x,b.a-a.x),a.l+b.d);
return ans;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin>>n;
    cin>>s;
    build(1,0,n-1);
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>x>>y;
        cout<<query(1,0,n-1,x-1,y-1).a<<endl;
    }
    return 0;
}

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