Submission #1203750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203750		nh0902	Election (BOI18_election)	C++20	0 / 100	1 ms	832 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 200010;

const int inf = 1e13;

int n, a[N], bit[N];

void update(int u, int v) {
    int idx = u;
    while (idx <= n) {
        bit[idx] += v;
        idx += (idx & (-idx));
    }
}

int getSum(int p) {
    int idx = p, ans = 0;
    while (idx > 0) {
        ans += bit[idx];
        idx -= (idx & (-idx));
    }
    return ans;
}

struct Segtree {
    vector<int> x, st, st_l, st_r;

    Segtree(int m) {
        x.assign(m, 0);
        st.assign(4 * m, 0);
        st_l.assign(4 * m, 0);
        st_r.assign(4 * m, 0);
    }

    void build(int id, int l, int r) {
        if (l == r) {
            st[id] = x[l];
            st_l[id] = l;
            st_r[id] = r;
            return;
        }

        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);

        st[id] = max(st[id * 2], st[id * 2 + 1]);
        if (st[id * 2] == st[id * 2 + 1]) {
            st_l[id] = st_l[id * 2];
            st_r[id] = st_r[id * 2 + 1];
        } else if (st[id * 2] < st[id * 2 + 1]) {
            st_l[id] = st_l[id * 2 + 1];
            st_r[id] = st_r[id * 2 + 1];
        } else {
            st_l[id] = st_l[id * 2];
            st_r[id] = st_r[id * 2];
        }
    }

    pair<int, int> get_l(int id, int l, int r, int u, int v) {
        if (r < u || v < l) return {- inf, 0};

        if (u <= l && r <= v) {
            return {st[id], st_l[id]};
        }

        int mid = (l + r) / 2;
        pair<int, int> ans_1 = get_l(id * 2, l, mid, u, v);
        pair<int, int> ans_2 = get_l(id * 2 + 1, mid + 1, r, u, v);

        if (ans_1.second < ans_2.second) return ans_2;
        return ans_1;
    }

    pair<int, int> get_r(int id, int l, int r, int u, int v) {
        if (r < u || v < l) return {- inf, 0};

        if (u <= l && r <= v) {
            return {st[id], st_r[id]};
        }

        int mid = (l + r) / 2;
        pair<int, int> ans_1 = get_r(id * 2, l, mid, u, v);
        pair<int, int> ans_2 = get_r(id * 2 + 1, mid + 1, r, u, v);

        if (ans_1.second > ans_2.second) return ans_1;
        return ans_2;
    }

} ;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    char c;
    for (int i = 1; i <= n; i ++) {
        cin >> c;
        if (c == 'T') {
            a[i] = 1;
            update(i, 1);
        } else {
            a[i] = - 1;
        }
    }

    Segtree seg1(n + 10), seg2(n + 10);

    int cur = 0;
    for (int i = 1; i <= n; i ++) {
        cur += a[i];
        seg1.x[i] = cur;
    }
    seg1.build(1, 1, n);

    cur = 0;
    for (int i = n; i >= 1; i --) {
        cur += a[i];
        seg2.x[i] = cur;
    }
    seg2.build(1, 1, n);

    int q, l, r;
    cin >> q;
    while (q --) {
        cin >> l >> r;
        pair<int, int> m1 = seg1.get_l(1, 1, n, l, r);
        pair<int, int> m2 = seg2.get_r(1, 1, n, l, r);

        if (m1.first == - inf && m2.first == - inf) {
            cout << 0 << "\n";
        } else if (m1.first == - inf) {
            cout << seg2.x[m2.second] - seg2.x[r + 1] << "\n";
        } else if (m2.first == - inf) {
            cout << seg1.x[m1.second] - seg1.x[l - 1] << "\n";
        } else {
            cout << max(seg1.x[m1.second] - seg1.x[l - 1], seg2.x[m2.second] - seg2.x[r + 1]) << "\n";
        }
    }

    return 0;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18