Submission #1254032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254032		armashka	Election (BOI18_election)	C++20	0 / 100	13 ms	23872 KiB

election

#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6 + 5;
const ll mod = 1e9 + 7;
const ld eps = 1e-6;
const ld Pi = acos(-1.0);

int n, q;
string s;
int L[N], R[N];
int ans[N];
vector<pair<int, int>> g[N];

int t[N * 4];

void upd(int pos, int val, int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v] += val;
        return;
    }

    int tm = (tl + tr) / 2;
    if (pos <= tm)
        upd(pos, val, v + v, tl, tm);
    else
        upd(pos, val, v + v + 1, tm + 1, tr);
    t[v] = t[v + v] + t[v + v + 1];
}

int get(int l, int r, int v, int tl, int tr)
{
    if (r < tl || tr < l)
        return 0;
    if (l <= tl && tr <= r)
        return t[v];
    int tm = (tl + tr) / 2;
    return get(l, r, v + v, tl, tm) + get(l, r, v + v + 1, tm + 1, tr);
}

void solve()
{
    cin >> n >> s;
    s = " " + s;

    stack<int> st;
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == 'C')
        {
            L[i] = i;
            st.push(i);
        }
        else
        {
            if (st.empty())
                L[i] = 0;
            else
            {
                L[i] = st.top();
                st.pop();
            }
        }
    }

    while (sz(st))
        st.pop();

    for (int i = n; i >= 1; --i)
    {
        if (s[i] == 'C')
        {
            R[i] = i;
            st.push(i);
        }
        else
        {
            if (st.empty())
                R[i] = n + 1;
            else
            {
                R[i] = st.top();
                st.pop();
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        g[R[i]].pb({L[i], 1});
    }

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

    for (int i = 1; i <= n; ++i)
    {
        for (auto [x, type] : g[i])
        {
            if (type == 1)
                upd(x, 1, 1, 1, n);
            else
                ans[-type] -= get(x, i, 1, 1, n);
        }
    }

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;

    // cin >> tt;
    for (int i = 1; i <= tt; ++i)
    {
        solve();
    }

    return 0;
}

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