Submission #486938

#	Time	Username	Problem	Language	Result	Execution time	Memory
486938		Victor	Election (BOI18_election)	C++17	0 / 100	4 ms	460 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

string str;

struct Node {
    Node *l,*r;
    int lo,hi,sum,best,pref,suf;
    Node(int L,int R) : lo(L), hi(R) {
        if(hi-lo==1){
            sum=str[lo]=='C'?-1:1;
            best=pref=suf=max(sum,0);

        } else {
            int mid=(lo+hi)/2;
            l=new Node(lo,mid);
            r=new Node(mid,hi);

            best=max(max(l->best+r->sum,l->sum+r->best),l->pref+r->suf);
            sum=l->sum+r->sum;
            pref=max(l->pref,l->sum+r->pref);
            suf=max(r->suf,r->sum+l->suf);
        }

        //cout<<"lo = "<<lo<<" hi = "<<hi<<endl;
        //cout<<"sum = "<<sum<<" best = "<<best<<" pref = "<<pref<<" suf = "<<suf<<endl;
        //cout<<endl;
    }

    pair<ii,ii>query(int L,int R){
        if(hi<=L||R<=lo)return {{0,0},{0,0}};
        if(L<=lo&&hi<=R)return {{sum,best},{pref,suf}};

        int lsum,lbest,lpref,lsuf;
        auto val=l->query(L,R);
        tie(lsum,lbest)=val.first;
        tie(lpref,lsuf)=val.second;

        int rsum,rbest,rpref,rsuf;
        val=r->query(L,R);
        tie(rsum,rbest)=val.first;
        tie(rpref,rsuf)=val.second;

        int cur_sum=lsum+rsum;
        int cur_best=max(max(lbest+rsum,lsum+rbest),lpref+rsuf);
        int cur_pref=max(l->pref,l->sum+r->pref);
        int cur_suf=max(r->suf,r->sum+l->suf);

        return {{cur_sum,cur_best},{cur_pref,cur_suf}};
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n,q;
    cin>>n>>str>>q;

    Node segtree(0,n);
    //cout<<segtree.sum<<' '<<segtree.best<<' '<<segtree.pref<<' '<<segtree.suf<<endl;

    while(q--){
        int lo,hi;
        cin>>lo>>hi;
        cout<<segtree.query(lo-1,hi).first.second<<endl;
    }
    return 0;
}

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