oj.uz

Submission #981875

# Submission time Handle Problem Language Result Execution time Memory
981875 2024-05-13T15:55:54 Z LOLOLO Election (BOI18_election) C++17
100 / 100
 762 ms 70580 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e6 + 30;
const int M = 5e5 + 5;
int cnt = 0;
int psum[N];
vector <pair <int, int>> ask[N];
int pos[N], n, ans[M];

struct seg{
    vector <int> laz, seg;
    void ass(int n) {
        laz.assign(n * 4 + 100, 0);
        seg.assign(n * 4 + 100, 0);
    }

    void push(int id) {
        int t = laz[id];
        laz[id * 2] += t;
        laz[id * 2 + 1] += t;
        seg[id * 2] += t;
        seg[id * 2 + 1] += t;
        laz[id] = 0;
    }

    void upd(int id, int l, int r, int u, int v, int c) {
        if (l > v || r < u)
            return;

        if (l >= u && r <= v) {
            seg[id] += c;
            laz[id] += c;
            return;
        }

        push(id);
        int m = (l + r) / 2;
        upd(id * 2, l, m, u, v, c);
        upd(id * 2 + 1, m + 1, r, u, v, c);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }

    int get(int id, int l, int r, int u, int v) {
        if (u == v && u == n + 1)
            return 0;

        if (l > v || r < u)
            return -1e9;

        if (l >= u && r <= v) {
            return seg[id];
        }

        push(id);
        int m = (l + r) / 2;
        return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
    }
};

struct fen{
    vector <int> f;
    int n;
    void ass(int N) {
        n = N;
        f.assign(n + 1, 0);
    }

    void upd(int i, int x) {
        for (; i <= n; i += i & (-i))
            f[i] += x;
    }

    int get(int i) {
        int s = 0;
        for (; i; i -= i & (-i))
            s += f[i];

        return s;
    }

    int range(int l, int r) {
        return get(r) - get(l - 1);
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fen f;
    seg st;
    cin >> n;
    st.ass(n);
    f.ass(n);

    psum[0] = M;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        
        if (c == 'T') {
            st.upd(1, 1, n, 1, i, 1);
            psum[i]++;
        } else {
            psum[i]--;
            st.upd(1, 1, n, 1, i, -1);
        }

        psum[i] += psum[i - 1];
    }

    int q;
    cin >> q;
 
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        ask[l - 1].pb({r, i});
    }

    pos[psum[n]] = n;

    for (int i = n - 1; i >= 0; i--) {
        if (psum[i] < psum[i + 1]) {
            int p = pos[psum[i] + 1];
            st.upd(1, 1, n, 1, p, -1);
            f.upd(p, 1);
        } else {
            int p = pos[psum[i]];
            if (p) {
                st.upd(1, 1, n, 1, p, 1);
                f.upd(p, -1);
            }
        }

        pos[psum[i]] = i;
        for (auto x : ask[i]) {
            ans[x.s] = f.range(i + 1, x.f) + max(0, st.get(1, 1, n, i + 1, x.f) - st.get(1, 1, n, x.f + 1, x.f + 1));
        }
    }

    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31324 KB Output is correct
2 Correct 8 ms 31392 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31396 KB Output is correct
5 Correct 8 ms 31324 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31324 KB Output is correct
2 Correct 8 ms 31392 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31396 KB Output is correct
5 Correct 8 ms 31324 KB Output is correct
6 Correct 83 ms 36564 KB Output is correct
7 Correct 85 ms 36036 KB Output is correct
8 Correct 79 ms 35980 KB Output is correct
9 Correct 78 ms 36252 KB Output is correct
10 Correct 82 ms 36436 KB Output is correct
11 Correct 83 ms 36568 KB Output is correct
12 Correct 82 ms 36564 KB Output is correct
13 Correct 82 ms 36436 KB Output is correct
14 Correct 80 ms 36568 KB Output is correct
15 Correct 78 ms 36436 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31324 KB Output is correct
2 Correct 8 ms 31392 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31396 KB Output is correct
5 Correct 8 ms 31324 KB Output is correct
6 Correct 83 ms 36564 KB Output is correct
7 Correct 85 ms 36036 KB Output is correct
8 Correct 79 ms 35980 KB Output is correct
9 Correct 78 ms 36252 KB Output is correct
10 Correct 82 ms 36436 KB Output is correct
11 Correct 83 ms 36568 KB Output is correct
12 Correct 82 ms 36564 KB Output is correct
13 Correct 82 ms 36436 KB Output is correct
14 Correct 80 ms 36568 KB Output is correct
15 Correct 78 ms 36436 KB Output is correct
16 Correct 723 ms 69488 KB Output is correct
17 Correct 616 ms 65620 KB Output is correct
18 Correct 651 ms 66644 KB Output is correct
19 Correct 635 ms 68092 KB Output is correct
20 Correct 725 ms 68844 KB Output is correct
21 Correct 733 ms 70508 KB Output is correct
22 Correct 762 ms 70352 KB Output is correct
23 Correct 719 ms 70580 KB Output is correct
24 Correct 696 ms 70176 KB Output is correct
25 Correct 685 ms 69960 KB Output is correct