oj.uz

Submission #877129

# Submission time Handle Problem Language Result Execution time Memory
877129 2023-11-22T22:56:05 Z amin_2008 Election (BOI18_election) C++17
100 / 100
 1273 ms 89912 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

// author: amin_2008

#define ios          ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll           long long
#define vi           vector<int>
#define vs           vector<string>
#define vc           vector<char>
#define vl           vector<ll>
#define all(v)       v.begin(), v.end()
#define rall(v)      v.rbegin(), v.rend()
#define pb           push_back
#define bpc          __builtin_popcount
#define pii          pair<int, int>
#define pll          pair<ll, ll>
#define piii         pair<pii, int>
#define vpii         vector<pii>
#define vpll         vector<pll>
#define vvpii        vector<vpii>
#define vvi          vector<vector<int>>
#define vvl          vector<vector<ll>>
#define ins          insert
#define ts           to_string
#define F            first
#define S            second
#define lb           lower_bound
#define ub           upper_bound
#define ld           long double
#define ull          unsigned long long
#define endl         '\n'
//#define int          ll

using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
template<class T> using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll inf = 2e5 * 1e9;
const int mod = 1e9+7;
const int sz = 5e5+5;
const int N = 500001;
const int logg = 18;
const int P = 40000005;
const ll M = 8e5+5;

//int a[sz];
vi st[sz << 2]{vi(4)};

vi merge(vi a, vi b)
{
    vi res(4);
    res.front() = a.front() + b.front();
    res[1] = max(a[1], b[1] + a.front());
    res[2] = max(b[2], a[2] + b.front());
    res[3] = max(max(max(a[3] + b.front(), b[3] + a.front()), 0), a[1] + b[2]);
    return res;
}

string s;

void build(int l, int r, int in)
{
    if ( l == r )
    {
        int a = ( s[l] == 'T' ), b = a;
        if ( !b ) b--;
        st[in] = {b, a, a, a};
        return;
    }
    int mid = ( l + r ) >> 1;
    build(l, mid, in << 1);
    build(mid+1, r, in << 1 | 1);
    st[in] = merge(st[in << 1], st[in << 1 | 1]);
}

vi get(int a, int b, int l, int r, int in)
{
    if ( a > r or b < l )       return {0, 0, 0, 0};
    if ( a <= l and r <= b )    return st[in];
    int mid = ( l + r ) >> 1;
    return merge(get(a, b, l, mid, in << 1), get(a, b, mid+1, r, in << 1 | 1));
}

void solve()
{
    int n;
    cin >> n >> s;
    build(0, n - 1, 1);
    int q;
    cin >> q;
    while ( q-- )
    {
        int l, r;
        cin >> l >> r;
        l--, r--;
        cout << get(l, r, 0, n - 1, 1)[3] << endl;
    }
}

signed main()
{
    ios;
    //precompute();
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47448 KB Output is correct
2 Correct 18 ms 47588 KB Output is correct
3 Correct 15 ms 47584 KB Output is correct
4 Correct 16 ms 47452 KB Output is correct
5 Correct 16 ms 47452 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47448 KB Output is correct
2 Correct 18 ms 47588 KB Output is correct
3 Correct 15 ms 47584 KB Output is correct
4 Correct 16 ms 47452 KB Output is correct
5 Correct 16 ms 47452 KB Output is correct
6 Correct 127 ms 52816 KB Output is correct
7 Correct 116 ms 52820 KB Output is correct
8 Correct 119 ms 52940 KB Output is correct
9 Correct 103 ms 52916 KB Output is correct
10 Correct 117 ms 52768 KB Output is correct
11 Correct 118 ms 53144 KB Output is correct
12 Correct 122 ms 53192 KB Output is correct
13 Correct 126 ms 53076 KB Output is correct
14 Correct 135 ms 53076 KB Output is correct
15 Correct 118 ms 53080 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 47448 KB Output is correct
2 Correct 18 ms 47588 KB Output is correct
3 Correct 15 ms 47584 KB Output is correct
4 Correct 16 ms 47452 KB Output is correct
5 Correct 16 ms 47452 KB Output is correct
6 Correct 127 ms 52816 KB Output is correct
7 Correct 116 ms 52820 KB Output is correct
8 Correct 119 ms 52940 KB Output is correct
9 Correct 103 ms 52916 KB Output is correct
10 Correct 117 ms 52768 KB Output is correct
11 Correct 118 ms 53144 KB Output is correct
12 Correct 122 ms 53192 KB Output is correct
13 Correct 126 ms 53076 KB Output is correct
14 Correct 135 ms 53076 KB Output is correct
15 Correct 118 ms 53080 KB Output is correct
16 Correct 1273 ms 88832 KB Output is correct
17 Correct 999 ms 88660 KB Output is correct
18 Correct 1154 ms 88548 KB Output is correct
19 Correct 961 ms 88040 KB Output is correct
20 Correct 1199 ms 87716 KB Output is correct
21 Correct 1216 ms 89912 KB Output is correct
22 Correct 1234 ms 89532 KB Output is correct
23 Correct 1218 ms 89736 KB Output is correct
24 Correct 1251 ms 89416 KB Output is correct
25 Correct 1264 ms 88808 KB Output is correct