oj.uz

Submission #945230

# Submission time Handle Problem Language Result Execution time Memory
945230 2024-03-13T14:46:01 Z vjudge1 Election (BOI18_election) C++17
100 / 100
 363 ms 30352 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int SZ = 5e5+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n, a[SZ];
string s;

struct SegTree
{
    struct Node
    {
        int sum, pref, suff, res;
        Node operator + (const Node& other) const
        {
            Node cur;
            cur.sum = sum + other.sum;
            cur.pref = max(pref, sum + other.pref);
            cur.suff = max(other.suff, other.sum + suff);
            cur.res = max({ res + other.sum, other.res + sum, pref + other.suff });
            return cur;
        }
    } nodes[4*SZ];

    void build(int id = 1, int lo = 1, int hi = n)
    {
        if(lo == hi)
        {
            if(s[lo] == 'T') nodes[id] = {1, 1, 1, 1};
            else nodes[id] = {-1, 0, 0, 0};
            return;
        }
        int mid = (lo + hi) / 2;
        build(2*id, lo, mid);
        build(2*id+1, mid+1, hi);
        nodes[id] = nodes[2*id] + nodes[2*id+1];
    }

    Node query(int u, int v, int id = 1, int lo = 1, int hi = n)
    {
        if(lo > v || hi < u) return {0,0,0,0};
        if(lo >= u && hi <= v) return nodes[id];
        int mid = (lo + hi) / 2;
        return query(u, v, 2*id, lo, mid) + query(u,v, 2*id+1, mid+1, hi);
    }
} st;

int main()
{
    init();
    cin >> n >> s;
    s = " " + s;
    st.build();
    int q;
    cin >> q;
    while(q--)
    {
        int lo,hi;
        cin >> lo >> hi;
        cout << st.query(lo, hi).res << '\n';
    }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 37 ms 8016 KB Output is correct
7 Correct 34 ms 7884 KB Output is correct
8 Correct 35 ms 8012 KB Output is correct
9 Correct 31 ms 8024 KB Output is correct
10 Correct 36 ms 7908 KB Output is correct
11 Correct 37 ms 8000 KB Output is correct
12 Correct 39 ms 8024 KB Output is correct
13 Correct 37 ms 8012 KB Output is correct
14 Correct 36 ms 8012 KB Output is correct
15 Correct 36 ms 8016 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 37 ms 8016 KB Output is correct
7 Correct 34 ms 7884 KB Output is correct
8 Correct 35 ms 8012 KB Output is correct
9 Correct 31 ms 8024 KB Output is correct
10 Correct 36 ms 7908 KB Output is correct
11 Correct 37 ms 8000 KB Output is correct
12 Correct 39 ms 8024 KB Output is correct
13 Correct 37 ms 8012 KB Output is correct
14 Correct 36 ms 8012 KB Output is correct
15 Correct 36 ms 8016 KB Output is correct
16 Correct 339 ms 29176 KB Output is correct
17 Correct 300 ms 28936 KB Output is correct
18 Correct 318 ms 29172 KB Output is correct
19 Correct 285 ms 28664 KB Output is correct
20 Correct 362 ms 28404 KB Output is correct
21 Correct 363 ms 30208 KB Output is correct
22 Correct 345 ms 29948 KB Output is correct
23 Correct 358 ms 30352 KB Output is correct
24 Correct 355 ms 29940 KB Output is correct
25 Correct 331 ms 29432 KB Output is correct