(POI) XXI OI Round I Task Salad Bar

https://szkopul.edu.pl/problemset/problem/d30xri2XGeuQ45CDrB7DWijK/site/?key=statement

#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
using namespace std;

#define prev kirino

const int N = 1000006;
const int NN = 2*N;

int Val(int x)
{
    return x+N;
}

int rVal(int x)
{
    return x-N;
}

int suf[N];
int sufiter[NN];
vector<int> sufv[NN];
int suf_left[N];

int pre[N];
int preiter[NN];
vector<int> prev[NN];

int a[N];
char s[N];

int mn[4*N];

void build(int now,int L,int R)
{
    if (L == R)
    {
        mn[now] = suf_left[L];
        return;
    }
    int mid=(L+R)>>1;
    build((now<<1),L,mid);
    build(((now<<1)|1),mid+1,R);
    mn[now] = min(mn[(now<<1)],mn[((now<<1)|1)]);
}

const int INF = (1<<30);

int query2(int now,int L,int R,int left)
{
    if (L==R)
    {
        return (suf_left[L]>left?0:L);
    }
    int mid=(L+R)>>1;
    if (mn[((now<<1)|1)] <= left) return query2(((now<<1)|1),mid+1,R,left);
    else return query2((now<<1),L,mid,left);
}

int query(int now,int L,int R,int l,int r,int left)
{
    if (l <= L && R <= r)
    {
        if (mn[now] > left) return 0;
        else return query2(now,L,R,left);
    }
    int mid=(L+R)>>1;
    //[L,mid] [mid+1,R]
    //[l,r]
    if (mid+1 > r) return query((now<<1),L,mid,l,r,left);
    else if (l > mid) return query(((now<<1)|1),mid+1,R,l,r,left);
    int ret = 0;
    if ((ret = query(((now<<1)|1),mid+1,R,l,r,left)) != 0) return ret;
    else return query((now<<1),L,mid,l,r,left);
}

int main ()
{
    int n;
    scanf("%d\n",&n);
    scanf("%s",s);
    for (int i=1;n>=i;++i)
    {
        a[i] = (s[i-1] == 'p' ? 1 : -1);
        pre[i] = pre[i-1] + a[i];
        prev[Val(pre[i])].push_back(i);
    }
    for (int i=n;i>=1;--i)
    {
        suf[i] = suf[i+1] + a[i];
        sufv[Val(suf[i])].push_back(i);
    }
    for (int i=n;i>=1;--i)
    {
        int q=Val(suf[i+1]-1);
        int left = n+1;
        if (sufiter[q] == sufv[q].size()) left = 1;
        else left = sufv[q][sufiter[q]]+1;
        sufiter[Val(suf[i])]++;
        if (left != i+1)
        {
            suf_left[i] = left;
        }
        else
        {
            suf_left[i] = INF;
        }
    }
    build(1,1,n);
    int ans=0;
    int mx=0;
    for (int i=1;n>=i;++i)
    {
        int q=Val(pre[i-1]-1);
        int right = 0;
        if (preiter[q] == prev[q].size()) right = n;
        else right = prev[q][preiter[q]]-1;
        preiter[Val(pre[i])]++;
        if (right != i-1)
        {
            int ret=query(1,1,n,i,right,i);
            if (ret != 0)
            {
                ans = max(ans,ret-i+1);
            }
        }
    }
    printf("%d\n",ans);
}