Submission #1270293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270293		BigBadBully	Election (BOI18_election)	C++20	28 / 100	3089 ms	2828 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;
    while(q--)
    {
        int l,r;
        cin >> l >> r;
        --l,--r;
        int sum = 0;
        vector<int> grt;
        int ans = 0;
        for (int i = l; i <= r; i++)
        {
            sum+=v[i];
            if(sum<0)
            {
                grt.push_back(1);
                ans++;
                sum=  0;
            }
            else
                grt.push_back(0);
        }
        sum = 0;
        for (int i = r; i >= l; i--)
        {
            sum+=v[i]+grt[i-l];
            if(sum<0)
            {
                ans++;
                sum = 0;
            }
        }
        cout << ans << '\n';
    }
}

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

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