Submission #1270277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270277		BigBadBully	Election (BOI18_election)	C++20	0 / 100	4 ms	1088 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)
    {
        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 = -n; i <= n; i++)
        idxs[i].push_back(n);
    for (int i = -1; i >= -n; i--)
        if (idxs[i].size()>1)
        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]];
            mile.update(idxs[pref[i]][p],idxs[pref[i]][p+1]-1,1);
        }
        idx[pref[i]]++;
        if (idx[sum] >= idxs[sum].size()-1)continue;
        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