oj.uz

Submission #154572

# Submission time Handle Problem Language Result Execution time Memory
154572 2019-09-22T18:47:11 Z dolphingarlic Election (BOI18_election) C++14
0 / 100
 3 ms 504 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
    int l_min, r_min, tot, overlap;

    Node operator+(Node b) {
        Node ret;
        ret.l_min = min(l_min, tot + b.l_min);
        ret.r_min = min(r_min + b.tot, b.r_min);
        ret.tot = tot + b.tot;
        ret.overlap = max(max(overlap - b.tot, b.overlap - tot), l_min + b.r_min);
        return ret;
    }
};

Node segtree[400001];
char s[100001];
int n;

void build(int node = 1, int l = 1, int r = n) {
    if (l == r) {
        if (s[l] == 'T') segtree[node] = {1, 1, -1, 1};
        else segtree[node] = {0, 0, 1, 0};
    } else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}

Node query(int a, int b, int node = 1, int l = 1, int r = n) {
    if (l > b || r < a) return {0, 0, 0, 0};
    if (l >= a && r <= b) return segtree[node];
    int mid = (l + r) / 2;
    return query(a, b, node * 2, l, mid) + query(a, b, node * 2 + 1, mid + 1, r);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    FOR(i, 1, n + 1) cin >> s[i];
    build();
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b).overlap << '\n';
    }
    return 0;
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -