oj.uz

Submission #480014

# Submission time Handle Problem Language Result Execution time Memory
480014 2021-10-14T09:10:12 Z SlavicG Election (BOI18_election) C++17
0 / 100
 2 ms 332 KB 
#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.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";
    }

}   
 
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -