Submission #1270286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270286		BigBadBully	Election (BOI18_election)	C++20	0 / 100	3 ms	832 KiB

election

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>

#define ff first
#define ss second
const int inf = 3e18;
using namespace std;
using ld = long double;
/*
struct seggy
{
    int n;
    vector<int> tree;
    seggy(int sz)
    {
        n = sz;
        tree.resize(4*n,0);
    }
    int query(int l,int r,int L,int R,int idx)
    {
        if (l>R||r<L)return 0ll;
        if (l>=L&&r<=R)return tree[idx];
        int mid = l+r>>1;
        return query(l,mid,L,R,2*idx)+query(mid+1,r,L,R,2*idx+1);
    }
    int query(int l,int r)
    {
        return query(0,n-1,l,r,1);
    }
    void update(int l,int r,int i,int x,int idx)
    {
        if (l>i||r<i)return;
        if(l==r)
        {
            tree[idx] = x;
            return;
        }

        int mid = l+r>>1;
        update(l,mid,i,x,2*idx);
        update(mid+1,r,i,x,2*idx+1);
        tree[idx] = tree[2*idx]+tree[2*idx+1];
    }
    void update(int i,int x)
    {
        update(0,n-1,i,x,1);
    }
};
*/
struct lijen
{
    int n;
    vector<int> tree, lazy;
    lijen(int sz)
    {
        n = sz;
        tree.resize(4 * n, 0);
        lazy.resize(4 * n, 0);
    }
    void pass(int l, int r, int idx)
    {
        if (lazy[idx] == 0)
            return;
        tree[idx] += lazy[idx];
        if (l != r)
        {
            lazy[2 * idx] += lazy[idx];
            lazy[2 * idx + 1] += lazy[idx];
        }
        lazy[idx] = 0;
    }
    int query(int l, int r, int L, int R, int idx)
    {
        pass(l, r, idx);
        if (l > R || r < L)
            return inf;
        if (l >= L && r <= R)
            return tree[idx];
        int mid = l + r >> 1;
        return min(query(l, mid, L, R, 2 * idx), query(mid + 1, r, L, R, 2 * idx + 1));
    }
    int query(int l, int r)
    {
        return query(0, n - 1, l, r, 1);
    }
    void update(int l, int r, int L, int R, int x, int idx)
    {
        pass(l, r, idx);
        if (l > R || r < L)
            return;
        if (l >= L && r <= R)
        {
            lazy[idx] += x;
            pass(l, r, idx);
            return;
        }
        int mid = l + r >> 1;
        update(l, mid, L, R, x, 2 * idx);
        update(mid + 1, r, L, R, x, 2 * idx + 1);
        tree[idx] = min(tree[2 * idx], tree[2 * idx + 1]);
    }
    void update(int l, int r, int x)
    {
        if(l>r)return;
        update(0, n - 1, l, r, x, 1);
    }
};

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> v(n, -1);
    for (int i = 0; i < n; i++)
        if (s[i] == 'C')
            v[i] += 2;
    int q;
    cin >> q;
    vector<array<int, 3>> quers(q);
    for (int i = 0; i < q; i++)
        cin >> quers[i][0] >> quers[i][1], quers[i][2] = i;
    sort(quers.begin(), quers.end());
    vector<int> ans(q);
    for (auto &a : quers)
        a[0]--, a[1]--;
    vector<int> pref(n), suf(n);
    pref[0] = v[0];
    for (int i = 1; i < n; i++)
        pref[i] = v[i] + pref[i - 1];
    suf[n - 1] = v[n - 1];
    for (int i = n - 2; i >= 0; i--)
        suf[i] = suf[i + 1] + v[i];
    lijen mile(n), nane(n);
    for (int i = 0; i < n; i++)
        mile.update(i, i, suf[i]), nane.update(i, i, pref[i]);
    map<int, int> idx;
    map<int, vector<int>> idxs;
    for (int i = 0; i < n; i++)
        idxs[pref[i]].push_back(i);
    for (int i = -1; i >= -n; i--)
        if (idxs[i].size() > 0)
            mile.update(0, idxs[i][0], 1);
    int sum = 0;
    int j = 0;
    auto print = [&]()
    {
        for (int i = 0; i < n; i++)
        {
            cout << mile.query(i, i) << ' ';
        }
        cout << '\n';
        for (int i = 0; i < n; i++)
            cout << nane.query(i, i) << ' ';
        cout << "\n\n";
    };
    for (int i = 0; i < n; i++)
    {
        //print();
        while (j < q && quers[j][0] == i)
        {
            int l = quers[j][0], r = quers[j][1];
            ans[quers[j][2]] = max(0ll, -(nane.query(l, r) - (l > 0 ? pref[l - 1] : 0))) + 
            max(0ll, -(mile.query(l, r) - (r < n - 1 ? mile.query(r + 1, r + 1) : 0)));
            j++;
        }
        if (pref[i] < sum)
        {
            int p = idx[pref[i]];
            if(p+1 >= idxs[pref[i]].size())
                mile.update(0,idxs[pref[i]][p], -1);
            else
                mile.update(idxs[pref[i]][p]+1, idxs[pref[i]][p + 1], 1);
        }
        idx[pref[i]]++;
        if (idx[sum] < idxs[sum].size())
        {
            int val = idxs[sum][idx[sum]];
            if (v[i] < 0)
                mile.update(0, val, -1);
            else
                mile.update(0, val, 1);
        }
        sum += v[i];
    }
    for (int x : ans)
        cout << x << '\n';
}

signed main()
{
    //ios::sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

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