Submission #481167

#	Time	Username	Problem	Language	Result	Execution time	Memory
481167		Karabasan	Election (BOI18_election)	C++17	100 / 100	1681 ms	29924 KiB

election

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
const int N = 5e5;
struct node{
    int pref;
    int suf;
    int sum;
    int ans;
};
 
node t[4 * N];
int a[N];
 
node merge(node a, node b){
    node c;
    c.sum = a.sum + b.sum;
    c.pref = max(a.pref, a.sum + b.pref);
    c.suf = max(b.suf, b.sum + a.suf);
    c.ans = max({0, a.pref + b.suf, a.sum + b.ans, b.sum + a.ans});
 
    return c;
}
void build(int i, int l, int r)
{
    if(l == r){
        t[i].pref = t[i].suf = max(0, a[l]);
        t[i].sum = a[l];
        t[i].ans = max(0, a[l]);
        return;
    }
    int mid = (l + r) / 2;
 
    build(2 * i, l, mid);
    build(2 * i + 1, mid + 1, r);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
node neutral = {0, 0, 0, 0};
node query(int i, int l, int r, int tl, int tr)
{
    if(l > tr || r < tl)return neutral;
    if(l >= tl && r <= tr)return t[i];
 
    int mid = (l + r) / 2;
 
    return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
}
void solve()
{  
    int n, q;
    string s;
    cin >> n >> s >> q;
 
    for(int i = 0;i < n;++i){
        a[i] = (s[i] == 'C' ? -1 : 1);
    }
    build(1, 0, n - 1);
 
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        cout << query(1, 0, n - 1, l - 1, r - 1).ans << "\n";
    }
 
}   
 
int main()
{
    int t = 1;
    while(t--)
    {
        solve();
    }
}

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