제출 #1151940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151940		Hamed_Ghaffari	Election (BOI18_election)	C++20	100 / 100	908 ms	201372 KiB

election

#include<bits/stdc++.h>
using namespace std;

#define mid ((l+r)>>1)
#define lc id<<1
#define rc lc|1
#define pb push_back
#define SZ(x) int(x.size())
#define maxs(a,b) (a=max(a,b))
#define all(x) x.begin(), x.end()

const int MXN = 5e5+5;

int n, q, ps[MXN];
string s;

vector<int> add[MXN<<2], mx[MXN<<2];

void build(int l=1, int r=n+1, int id=1) {
    mx[id].pb(ps[l]-ps[l-1]);
    for(int i=l+1; i<r; i++) mx[id].pb(max(mx[id].back(), ps[i]-ps[l-1]));
    for(int i=l; i<r; i++)
        if(ps[i]-ps[l-1]==-SZ(add[id])-1)
            add[id].pb(i);
    vector<int> tmp;
    for(int i=SZ(add[id])-1; i>=0; i--) {
        tmp.pb(-1e9);
        if(SZ(tmp)>1) tmp.back() = tmp[SZ(tmp)-2]+1;
        for(int j=add[id][i]; j<(SZ(tmp)>1 ? add[id][i+1] : r); j++)
            maxs(tmp.back(), ps[j]-ps[l-1]+1);
    }
    reverse(all(tmp));
    for(int i=0; i<SZ(tmp); i++)
        maxs(tmp[i], mx[id][add[id][i]-l]);
    add[id] = tmp;
    if(r-l>1) build(l, mid, lc), build(mid, r, rc);
}
int CUR, MX;
void get(int s, int e, int l=1, int r=n+1, int id=1) {
    if(s<=l && r<=e) {
        if(CUR+ps[l-1]-ps[s-1]<SZ(add[id])) {
            maxs(MX, add[id][CUR+ps[l-1]-ps[s-1]]+CUR+ps[l-1]-ps[s-1]);
            CUR = SZ(add[id]) -ps[l-1] + ps[s-1];
        }
        else maxs(MX, mx[id].back()+CUR+ps[l-1]-ps[s-1]);
        return;
    }
    if(s<mid) get(s, e, l, mid, lc);
    if(e>mid) get(s, e, mid, r, rc);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> s >> q;
    for(int i=1; i<=n; i++) ps[i] = ps[i-1] + (s[i-1]=='C' ? 1 : -1);
    build();
    while(q--) {
        int l, r;
        cin >> l >> r;
        int cur=0, mx=0;
        for(int i=l; i<=r; i++) {
            if(ps[i]-ps[l-1]==-cur-1) cur++;
            mx = max(mx, ps[i]-ps[l-1]+cur);
        }
        CUR = MX = 0;
        get(l, r+1);
        cout << MX-ps[r]+ps[l-1] << '\n';
    }
    return 0;
}

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