Submission #1265816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265816		3m17	Election (BOI18_election)	C++20	100 / 100	984 ms	36616 KiB

election

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int Nmax = 5e5 + 26;
const int LogN = 18;

struct SegTree
{
    int Sum;
    int Pre;
    int Suf;
    int Ans;
};

int n , q;
string s;
SegTree ST[Nmax * 4];


SegTree Merge (SegTree a , SegTree b)
{
    SegTree ANS;
    ANS.Sum = a.Sum + b.Sum;
    ANS.Pre = max(a.Sum + b.Pre , a.Pre);
    ANS.Suf = max(a.Suf + b.Sum , b.Suf);
    ANS.Ans = max({a.Ans + b.Sum , a.Sum + b.Ans , a.Pre + b.Suf});

    return ANS;
}

void Build(int id , int l , int r)
{
    if(l == r)
    {
        if(s[l] == 'T') ST[id] = {1 , 1 , 1 , 1};
        else ST[id] = {-1 , 0 , 0 , 0};
        return;
    }

    int mid = (l + r) / 2;

    Build(id * 2 , l , mid);
    Build(id * 2 + 1 , mid + 1 , r);

    ST[id] = Merge(ST[id * 2] , ST[id * 2 + 1]);
}

SegTree Get (int id , int l , int r , int u , int v)
{
    if(r < u || l > v) return {0 , 0 , 0 , 0};

    if(u <= l && r <= v) return ST[id];

    int mid = (l + r) / 2;

    return Merge(Get(id * 2 , l , mid , u , v), Get(id * 2 + 1 , mid + 1 , r , u , v));
}

main()
{
    cin >> n >> s;
    s = ' ' + s;

    Build(1 , 1 , n);
    //cout << ST[1].Ans << ' ' << ST[1].Sum << ' ' << ST[1].Pre << ' ' << ST[1].Suf << '\n';
    cin >> q;
    for (int i = 1 ; i <= q ; i++)
    {
        int l , r;
        cin >> l >> r;
        int Ans = max(0LL , Get(1 , 1 , n , l , r).Ans);
        cout << Ans << '\n';
    }
}

/*
TC
TTTCCTTT
CCCTTTTTTCC

-1 -2 -3 -2 -1 0 1 2 3 2 1

11
CCCTTTTTTCC
3
1 11
4 9
1 6
*/

Compilation message (stderr)

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

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