oj.uz

Submission #836712

# Submission time Handle Problem Language Result Execution time Memory
836712 2023-08-24T14:25:48 Z abysmal Election (BOI18_election) C++14
100 / 100
 422 ms 28012 KB 
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>
#include<string.h>

using namespace std;

const int64_t INF = (int64_t) 1e18 + 100;
const int64_t mINF = (int64_t) 1e6 * 2 + 100;
const int64_t MOD = 1e9 + 7;
const int64_t MOD2 = 998244353;
const int nbit = 31;
const int ndig = 10;
const int nchar = 26;
const int D = 4;
int dr[D] = {-1, 0, 1, 0};
int dc[D] = {0, 1, 0, -1};
const int Dk = 8;
int drk[Dk] = {2, 2, -2, -2, 1, 1, -1, -1};
int dck[Dk] = {1, -1, 1, -1, 2, -2, 2, -2};

struct Node
{
    int mx;
    int sum;
    int pre;
    int suf;

    Node(int mx_, int sum_, int pre_, int suf_) : mx(mx_), sum(sum_), pre(pre_), suf(suf_) {}
};

struct Solution
{
    int n;
    string s;
    vector<Node> tree;
    Solution() {}

    void solve()
    {
        cin >> n >> s;
        while(__builtin_popcount(n) != 1) n++;
        tree.resize(2 * n, Node(0, 0, 0, 0));

        for(int i = 0; i < (int) s.length(); i++)
        {
            if(s[i] == 'T') tree[n + i] = Node(1, 1, 1, 1);
            else tree[n + i] = Node(0, -1, 0, 0);
        }

        for(int i = n - 1; i >= 1; i--)
        {
            tree[i] = combine(tree[i * 2], tree[i * 2 + 1]);
        }

        int q;
        cin >> q;
        for(int i = 0; i < q; i++)
        {
            int l;
            int r;
            cin >> l >> r;
            l--; r--;

            cout << get(1, 0, n - 1, l, r).mx << "\n";
        }
    }

    Node get(int node, int nleft, int nright, int left, int right)
    {
        if(left > nright || nleft > right) return Node(0, 0, 0, 0);
        if(left <= nleft && nright <= right) return tree[node];

        int mid = nleft + (nright - nleft) / 2;
        return combine(get(node * 2, nleft, mid, left, right),
                       get(node * 2 + 1, mid + 1, nright, left, right));
    }

    Node combine(Node left, Node right)
    {
        Node now(0, 0, 0, 0);
        now.sum = left.sum + right.sum;
        now.pre = max(left.pre, left.sum + right.pre);
        now.suf = max(right.suf, right.sum + left.suf);
        now.mx = max({left.mx + right.sum, left.sum + right.mx, left.pre + right.suf});
        return now;
    }

    void modadd(int& t1, int t2)
    {
        t1 += t2;
        if(t1 >= MOD) t1-= MOD;
        return;
    }

    void modsub(int& t1, int t2)
    {
        t1 -= t2;
        if(t1 < 0) t1 += MOD;
        return;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return res % MOD;
    }

    int Abs(int tmp)
    {
        if(tmp < 0) return -tmp;
        return tmp;
    }

    int MASK(int j)
    {
        return (1 << j);
    }

    int BIT(int tmp, int j)
    {
        int x = tmp & MASK(j);
        if(x != 0) return 1;
        return 0;
    }
};

void __setup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __setup();

    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }
    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 39 ms 5732 KB Output is correct
7 Correct 35 ms 5648 KB Output is correct
8 Correct 35 ms 5712 KB Output is correct
9 Correct 43 ms 5820 KB Output is correct
10 Correct 37 ms 5684 KB Output is correct
11 Correct 37 ms 5780 KB Output is correct
12 Correct 37 ms 5888 KB Output is correct
13 Correct 37 ms 5920 KB Output is correct
14 Correct 37 ms 5768 KB Output is correct
15 Correct 36 ms 5816 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 39 ms 5732 KB Output is correct
7 Correct 35 ms 5648 KB Output is correct
8 Correct 35 ms 5712 KB Output is correct
9 Correct 43 ms 5820 KB Output is correct
10 Correct 37 ms 5684 KB Output is correct
11 Correct 37 ms 5780 KB Output is correct
12 Correct 37 ms 5888 KB Output is correct
13 Correct 37 ms 5920 KB Output is correct
14 Correct 37 ms 5768 KB Output is correct
15 Correct 36 ms 5816 KB Output is correct
16 Correct 377 ms 26920 KB Output is correct
17 Correct 280 ms 26592 KB Output is correct
18 Correct 335 ms 26768 KB Output is correct
19 Correct 298 ms 26308 KB Output is correct
20 Correct 372 ms 26140 KB Output is correct
21 Correct 357 ms 27844 KB Output is correct
22 Correct 387 ms 27688 KB Output is correct
23 Correct 422 ms 28012 KB Output is correct
24 Correct 370 ms 27540 KB Output is correct
25 Correct 365 ms 27168 KB Output is correct