oj.uz

답안 #1024527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1024527 2024-07-16T07:00:05 Z michified Election (BOI18_election) C++17
100 / 100
 874 ms 39084 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() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 108 ms 5712 KB Output is correct
7 Correct 112 ms 5884 KB Output is correct
8 Correct 105 ms 5592 KB Output is correct
9 Correct 104 ms 5712 KB Output is correct
10 Correct 111 ms 5712 KB Output is correct
11 Correct 109 ms 5836 KB Output is correct
12 Correct 109 ms 5716 KB Output is correct
13 Correct 108 ms 5696 KB Output is correct
14 Correct 107 ms 5712 KB Output is correct
15 Correct 108 ms 5756 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 108 ms 5712 KB Output is correct
7 Correct 112 ms 5884 KB Output is correct
8 Correct 105 ms 5592 KB Output is correct
9 Correct 104 ms 5712 KB Output is correct
10 Correct 111 ms 5712 KB Output is correct
11 Correct 109 ms 5836 KB Output is correct
12 Correct 109 ms 5716 KB Output is correct
13 Correct 108 ms 5696 KB Output is correct
14 Correct 107 ms 5712 KB Output is correct
15 Correct 108 ms 5756 KB Output is correct
16 Correct 874 ms 38120 KB Output is correct
17 Correct 813 ms 38260 KB Output is correct
18 Correct 840 ms 38248 KB Output is correct
19 Correct 759 ms 37716 KB Output is correct
20 Correct 789 ms 37092 KB Output is correct
21 Correct 857 ms 39084 KB Output is correct
22 Correct 819 ms 38764 KB Output is correct
23 Correct 806 ms 39020 KB Output is correct
24 Correct 828 ms 38772 KB Output is correct
25 Correct 812 ms 38380 KB Output is correct