Submission #848842

#	Time	Username	Problem	Language	Result	Execution time	Memory
848842		ssense	Election (BOI18_election)	C++14	100 / 100	488 ms	44452 KiB

election

#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
#define int long long
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu

struct node
{
    int sum, pref, suff, ans;
    node(int ans_, int sum_, int pref_, int suff_) : ans(ans_), sum(sum_), pref(pref_), suff(suff_) {}
};

struct segtree
{
    int n;
    vector<node> tree;
    segtree(string s)
    {
        n = s.size();
        n = 1<<(32-__builtin_clz(n));
        tree.assign(2*n, node(0, 0, 0, 0));
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == 'T')
            {
                tree[i+n] = node(1, 1, 1, 1);
            }
            else
            {
                tree[i+n] = node(0, -1, 0, 0);
            }
        }
        for(int i = n-1; i >= 1; i--)
        {
            tree[i] = combine(tree[2*i], tree[2*i+1]);
        }
    }
    
    node combine(node a, node b)
    {
        node now = node(0, 0, 0, 0);
        now.sum = a.sum+b.sum;
        now.pref = max(a.pref, a.sum+b.pref);
        now.suff = max(b.suff, a.suff+b.sum);
        now.ans = max({a.pref+b.suff, a.sum+b.ans, a.ans+b.sum});
        return now;
    }
    
    node get(int i, int l, int r, int tl, int tr)
    {
        if(tr < l)
        {
            return node(0, 0, 0, 0);
        }
        if(tl > r)
        {
            return node(0, 0, 0, 0);
        }
        if(tl <= l && tr >= r)
        {
            return tree[i];
        }
        int mid = l+r>>1;
        return combine(get(2*i, l, mid, tl, tr), get(2*i+1, mid+1, r, tl, tr));
    }
    
    node query(int l, int r)
    {
        return get(1, 0, n-1, l, r);
    }
};

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    segtree bruh(s);
    int q;
    cin >> q;
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        cout << bruh.query(l, r).ans << endl;
    }
}

int32_t main(){
    startt
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}



/*
11
CCCTTTTTTCC
3
1 11
4 9
1 6
 
 
 */

Compilation message (stderr)

election.cpp: In member function 'void prefix_sum::build(std::vector<long long int>)':
election.cpp:20:667: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         ~~^~~~~~~~~~
election.cpp: In constructor 'node::node(long long int, long long int, long long int, long long int)':
election.cpp:24:26: warning: 'node::ans' will be initialized after [-Wreorder]
   24 |     int sum, pref, suff, ans;
      |                          ^~~
election.cpp:24:9: warning:   'long long int node::sum' [-Wreorder]
   24 |     int sum, pref, suff, ans;
      |         ^~~
election.cpp:25:5: warning:   when initialized here [-Wreorder]
   25 |     node(int ans_, int sum_, int pref_, int suff_) : ans(ans_), sum(sum_), pref(pref_), suff(suff_) {}
      |     ^~~~
election.cpp: In constructor 'segtree::segtree(std::string)':
election.cpp:37:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int i = 0; i < s.size(); i++)
      |                        ~~^~~~~~~~~~
election.cpp: In member function 'node segtree::get(long long int, long long int, long long int, long long int, long long int)':
election.cpp:78:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         int mid = l+r>>1;
      |                   ~^~

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