Submission #480002

#	Time	Username	Problem	Language	Result	Execution time	Memory
480002		SlavicG	Election (BOI18_election)	C++17	0 / 100	5 ms	716 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()
 
#define int long long
template<typename T>
struct segment_tree{
    int n;
    vector<T> t, lazy, a;
    T neutral, lazy_neutral;
    function<T(const T&, const T&)> merge;
    function<T(const T&, const T&)> upd;
 
    bool range_modif = false;
    segment_tree(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif)
    {
        range_modif = _range_modif;
        init(_n, _neutral, _lazy_neutral, _merge, _upd);
    }
    segment_tree(vector<T> _a, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif)
    {
        range_modif = _range_modif;
        a = _a;
        int _n = (int)a.size();
        init(_n, _neutral, _lazy_neutral, _merge, _upd);
        build(1, 0, n - 1);
    }
 
    void init(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd)
    {
        n = _n;
        neutral = _neutral;
        lazy_neutral = _lazy_neutral;
        merge = _merge;
        upd = _upd;
        t.assign(4 * n, neutral);
        lazy.assign(4 * n, lazy_neutral);
    }
 
    void build(int i, int l, int r)
    {
        if(l == r)
        {
            t[i] = a[l];
            return;
        }
 
        int mid = l + r >> 1;
        build(2 * i, l, mid);
        build(2 * i + 1, mid + 1, r);
 
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
 
    void push(int i, int l, int r)
    {
        if(lazy[i] == lazy_neutral)return;
 
        t[i] = upd(t[i], lazy[i] * (range_modif ? (r - l + 1) : 1));
 
        if(l != r)
        {
            lazy[2 * i] = upd(lazy[2 * i], lazy[i]);
            lazy[2 * i + 1] = upd(lazy[2 * i + 1], lazy[i]);
        }
        lazy[i] = lazy_neutral;
    }
 
    void modif(int i, int l, int r, int tl, int tr, T val)
    {
        push(i, l, r);
        if(l > tr || r < tl)return;
 
        if(l >= tl && r <= tr)
        {
            lazy[i] = upd(lazy[i], val);
            push(i, l, r);
            return;
        }
 
        int mid = l + r >> 1;
 
        modif(2 * i, l, mid, tl, tr, val);
        modif(2 * i + 1, mid + 1, r, tl, tr, val);
 
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    T query(int i, int l, int r, int tl, int tr)
    {
        push(i, l, r);
        if(l > tr || r < tl)return neutral;
        if(l >= tl && r <= tr)return t[i];
 
        int mid = l + r >> 1;
 
        T left = query(2 * i, l, mid, tl, tr);
        T right = query(2 * i + 1, mid + 1, r, tl, tr);
 
        return merge(left, right);
    }
 
    void modif(int l, int r, T val){
        modif(1, 0, n - 1, l, r, val);
    }
    void modif(int poz, T val){
        modif(1, 0, n - 1, poz, poz, val);
    }
    T query(int l, int r){
        return query(1, 0, n - 1, l, r);
    }
    T query(int poz){
        return query(1, 0, n - 1, poz, poz);
    }
    //n, neutral, lazy neutral, merge, upd, bool range update
};
int mg(int a, int b){
    return min(a, b);
}
int sm(int a, int b){
    return a + b;
}
int up(int a, int b){
    a += b;
    return a;
}
void solve()
{  
    int n, q;
    string s;
    cin >> n >> s;
 
    segment_tree<int> a(n, 0, 0, mg, up, 0);
    segment_tree<int> b(n, 0, 0, mg, up, 0);
 
    segment_tree<int> sum_pref(n, 0, 0, sm, up, 1);
    segment_tree<int> sum_suf(n, 0, 0,  sm,  up, 1); 
 
 
    int p = 0;
    for(int i = 0;i < n;++i){
        int x = 0;
        if(s[i] == 'C')x = 1;
        else x = -1;
        p += x;
 
        a.modif(i, p);
        sum_pref.modif(i, x);
    }
    p = 0;
    for(int i = n - 1;i >= 0;--i){
        int x = 0;
        if(s[i] == 'C')x = 1;
        else x = -1;
        p += x;
        b.modif(i, p);
        sum_suf.modif(i, x);
    }
 
    cin >> q;
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        --l, --r;
 
        int ans_left = a.query(l, r);
        if(l)ans_left -= sum_pref.query(0, l - 1);
 
        int ans_right = b.query(l, r);
        if(r + 1 < n)ans_right -= sum_suf.query(r + 1, n - 1);
 
        cout << max(0LL, max(-ans_left, -ans_right)) << '\n';
 
    }     
}   
 
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}

Compilation message (stderr)

election.cpp: In instantiation of 'void segment_tree<T>::modif(long long int, long long int, long long int, long long int, long long int, T) [with T = long long int]':
election.cpp:114:14:   required from 'void segment_tree<T>::modif(long long int, T) [with T = long long int]'
election.cpp:154:21:   required from here
election.cpp:89:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int mid = l + r >> 1;
      |                   ~~^~~
election.cpp: In instantiation of 'T segment_tree<T>::query(long long int, long long int, long long int, long long int, long long int) [with T = long long int]':
election.cpp:117:21:   required from 'T segment_tree<T>::query(long long int, long long int) [with T = long long int]'
election.cpp:174:36:   required from here
election.cpp:102:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         int mid = l + r >> 1;
      |                   ~~^~~

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