Submission #1293039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293039		kkkk	Election (BOI18_election)	C++20	100 / 100	405 ms	20340 KiB

election

#include<bits/stdc++.h>
using namespace std;
string s;
int n;
const int N = 5e5+5;
struct Node
{
    int l,r,v,x;
} st[4*N];
Node merge(Node a,Node b)
{
   int L = max(a.l,a.v + b.l);
   int R = max(b.r,b.v + a.r);
   int v = a.v + b.v;
   int x = max(a.l + b.r,max(a.x + b.v,b.x + a.v));
   return {L,R,v,x};
}
Node get(int id,int l,int r,int u,int v)
{
   if(v < l or r < u)
    return {0,0,0,0};
   if(u <= l and r <= v)
     return st[id];
    int mid = (l+r)/2;
    return merge(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}
void update(int id,int l,int r,int pos,int v)
{
    if(l > pos or pos > r)
     return;
     if(l == r)
     {
       st[id].l = max(0,v);
       st[id].r = max(0,v);
       st[id].v = v;
       st[id].x = max(0,v);
       return;
     }
     int mid = (l+r)/2;
     update(2*id,l,mid,pos,v);
     update(2*id+1,mid+1,r,pos,v);
     st[id] = merge(st[2*id],st[2*id+1]);
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>s;
    for(int i = 0;i < s.size();i++)
    {
       // cin>>s[i];
        int t;
        if(s[i] == 'T')
           t = 1;
        else
            t = -1;
        update(1,1,n,i+1,t);
    }

    int q;
    cin>>q;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<get(1,1,n,l,r).x<<'\n';
    }

}

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