oj.uz

Submission #1100555

# Submission time Handle Problem Language Result Execution time Memory
1100555 2024-10-14T08:58:04 Z vjudge1 Election (BOI18_election) C++17
82 / 100
 187 ms 39500 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

const int MAXN = 3e5 + 10;

char c[MAXN];

struct Segment {
    
    struct Node {
        int pf, sf, sum, ans;
        Node()
        {
            pf = sf = sum = ans = 0;
        }
    } node[MAXN << 2];

    Node merge(Node l, Node r)
    {
        Node res;
        res.pf = max(l.pf, l.sum + r.pf);
        res.sf = max(r.sf, r.sum + l.sf);
        res.sum = l.sum + r.sum;
        res.ans = max(max(l.ans + r.sum, r.ans + l.sum), l.pf + r.sf);
        return res;
    }

    void initialize(int id, int l, int r)
    {
        if (l + 1 == r)
        {
            if (c[l] == 'T')
                node[id].pf = node[id].sf = node[id].sum = node[id].ans = 1;
            else
            {
                node[id].pf = node[id].sf = node[id].ans = 0;
                node[id].sum = -1;
            }
            return;
        }
        int mid = (l + r) >> 1;
        initialize(id << 1 | 0, l, mid);
        initialize(id << 1 | 1, mid, r);
        node[id] = merge(node[id << 1 | 0], node[id << 1 | 1]);
    }

    Node get(int id, int L, int R, int l, int r)
    {
        if (L == l && R == r)
        {
            return node[id];
        }
        int mid = (L + R) >> 1;
        Node res;
        if (l < mid)
            res = merge(res, get(id << 1 | 0, L, mid, l, min(r, mid)));
        if (r > mid)
            res = merge(res, get(id << 1 | 1, mid, R, max(l, mid), r));
        return res;
    }

} Seg;

int main()
{
    int n, q;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    Seg.initialize(1, 1, n + 1);
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        auto ans = Seg.get(1, 1, n + 1, l, r + 1);
        cout << ans.ans << endl;
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 8 ms 19024 KB Output is correct
5 Correct 7 ms 19036 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 8 ms 19024 KB Output is correct
5 Correct 7 ms 19036 KB Output is correct
6 Correct 156 ms 20048 KB Output is correct
7 Correct 153 ms 20312 KB Output is correct
8 Correct 150 ms 20316 KB Output is correct
9 Correct 152 ms 20336 KB Output is correct
10 Correct 161 ms 20308 KB Output is correct
11 Correct 155 ms 20556 KB Output is correct
12 Correct 187 ms 20560 KB Output is correct
13 Correct 187 ms 20568 KB Output is correct
14 Correct 157 ms 20568 KB Output is correct
15 Correct 172 ms 20312 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19036 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 8 ms 19024 KB Output is correct
5 Correct 7 ms 19036 KB Output is correct
6 Correct 156 ms 20048 KB Output is correct
7 Correct 153 ms 20312 KB Output is correct
8 Correct 150 ms 20316 KB Output is correct
9 Correct 152 ms 20336 KB Output is correct
10 Correct 161 ms 20308 KB Output is correct
11 Correct 155 ms 20556 KB Output is correct
12 Correct 187 ms 20560 KB Output is correct
13 Correct 187 ms 20568 KB Output is correct
14 Correct 157 ms 20568 KB Output is correct
15 Correct 172 ms 20312 KB Output is correct
16 Runtime error 40 ms 39500 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -