oj.uz

Submission #848842

# Submission time Handle Problem Language Result Execution time Memory
848842 2023-09-13T15:34:53 Z ssense Election (BOI18_election) C++14
100 / 100
 488 ms 44452 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 42 ms 9448 KB Output is correct
7 Correct 41 ms 9944 KB Output is correct
8 Correct 43 ms 9764 KB Output is correct
9 Correct 40 ms 9812 KB Output is correct
10 Correct 45 ms 9808 KB Output is correct
11 Correct 43 ms 10120 KB Output is correct
12 Correct 45 ms 9972 KB Output is correct
13 Correct 52 ms 10088 KB Output is correct
14 Correct 50 ms 10044 KB Output is correct
15 Correct 44 ms 9812 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 42 ms 9448 KB Output is correct
7 Correct 41 ms 9944 KB Output is correct
8 Correct 43 ms 9764 KB Output is correct
9 Correct 40 ms 9812 KB Output is correct
10 Correct 45 ms 9808 KB Output is correct
11 Correct 43 ms 10120 KB Output is correct
12 Correct 45 ms 9972 KB Output is correct
13 Correct 52 ms 10088 KB Output is correct
14 Correct 50 ms 10044 KB Output is correct
15 Correct 44 ms 9812 KB Output is correct
16 Correct 431 ms 43528 KB Output is correct
17 Correct 385 ms 42884 KB Output is correct
18 Correct 393 ms 43424 KB Output is correct
19 Correct 343 ms 42748 KB Output is correct
20 Correct 476 ms 42440 KB Output is correct
21 Correct 476 ms 44452 KB Output is correct
22 Correct 441 ms 44280 KB Output is correct
23 Correct 460 ms 44364 KB Output is correct
24 Correct 447 ms 44096 KB Output is correct
25 Correct 488 ms 43648 KB Output is correct