oj.uz

Submission #1024524

# Submission time Handle Problem Language Result Execution time Memory
1024524 2024-07-16T06:58:48 Z michified Election (BOI18_election) C++17
100 / 100
 1094 ms 46740 KB 
#include <bits/stdc++.h>
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;

struct node_t {
    int mp, ms, tot, ans;
};

string votes;
vector<node_t> st;

void merge(node_t& l, node_t& r, node_t& cur) {
    cur.mp = max(l.mp, r.mp + l.tot);
    cur.ms = max(l.ms + r.tot, r.ms);
    cur.tot = l.tot + r.tot;
    cur.ans = max(max(l.tot + r.ans, l.ans + r.tot), l.mp + r.ms);
}

void build(int id, int l, int r) {
    if (l == r) {
        if (votes[l] == 'T') st[id] = {1, 1, 1, 1};
        else st[id] = {0, 0, -1, 0};
        return;
    }
    int mid = (l + r) / 2;
    build(lid, l, mid);
    build(rid, mid + 1, r);
    merge(st[lid], st[rid], st[id]);
}

node_t quer(int id, int l, int r, int ql, int qr) {
    if (l > qr or r < ql) return {0, 0, 0, 0};
    if (ql <= l and r <= qr) return st[id];
    int mid = (l + r) / 2;
    node_t ret, L = quer(lid, l, mid, ql, qr), R = quer(rid, mid + 1, r, ql, qr);
    merge(L, R, ret);
    return ret;
}

int main() {
    int n, q, i;
    cin >> n >> votes >> q;
    vector<pair<int, int>> ques(q);
    for (i = 0; i < q; i++) cin >> ques[i].first >> ques[i].second;
    st.resize(n * 4);
    build(0, 0, n - 1);
    for (auto& que : ques) {
        que.first--;
        que.second--;
        cout << quer(0, 0, n - 1, que.first, que.second).ans << endl;
    }
    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 140 ms 6740 KB Output is correct
7 Correct 134 ms 6480 KB Output is correct
8 Correct 128 ms 6484 KB Output is correct
9 Correct 132 ms 6484 KB Output is correct
10 Correct 140 ms 6484 KB Output is correct
11 Correct 135 ms 6740 KB Output is correct
12 Correct 133 ms 6736 KB Output is correct
13 Correct 130 ms 6736 KB Output is correct
14 Correct 128 ms 6636 KB Output is correct
15 Correct 130 ms 6740 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 140 ms 6740 KB Output is correct
7 Correct 134 ms 6480 KB Output is correct
8 Correct 128 ms 6484 KB Output is correct
9 Correct 132 ms 6484 KB Output is correct
10 Correct 140 ms 6484 KB Output is correct
11 Correct 135 ms 6740 KB Output is correct
12 Correct 133 ms 6736 KB Output is correct
13 Correct 130 ms 6736 KB Output is correct
14 Correct 128 ms 6636 KB Output is correct
15 Correct 130 ms 6740 KB Output is correct
16 Correct 1094 ms 45904 KB Output is correct
17 Correct 968 ms 45392 KB Output is correct
18 Correct 1048 ms 45580 KB Output is correct
19 Correct 936 ms 45064 KB Output is correct
20 Correct 1053 ms 45024 KB Output is correct
21 Correct 1014 ms 46592 KB Output is correct
22 Correct 1084 ms 46544 KB Output is correct
23 Correct 1063 ms 46740 KB Output is correct
24 Correct 1067 ms 46564 KB Output is correct
25 Correct 993 ms 46088 KB Output is correct