Submission #1292973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292973		kkkk	Election (BOI18_election)	C++20	0 / 100	1 ms	332 KiB

election

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
struct Node
{
   int L,R,s,a;
}st[4*N];
char a[N];
int q,n;
Node merge(Node a,Node b)
{
    int x = max(a.L,a.s+ b.L);
    int y = max(b.R,b.s + a.R);
    int t = a.s + b.s;
    int k = max(a.L+b.R,max(a.a+b.s,b.a+a.s));
    return {x,y,t,k};
}
void update(int id,int l,int r,int i,int v)
{
    if(i < l or i > r)
        return;
    if(l == r)
    {
        st[id].L = max(st[id].L,v);
        st[id].R = max(st[id].R,v);
        st[id].s = v;
        if(v == 1)
        st[id].a = 1;
        else
        st[id].a = 0;
        return;
    }
    int mid = (l+r)/2;
    update(2*id,l,mid,i,v);
    update(2*id+1,mid+1,r,i,v);
    st[id] = merge(st[2*id],st[2*id+1]);
}
Node get(int id,int l,int r,int u,int v)
{
    if(v < l or r < u)
    return {0,0,0,0};
    if(u <= l and r <= v)
        return st[id];
    int mid = (l+r)/2;
    return merge(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1;i <= n;i++)
    {
        cin>>a[i];
        int v;
        if(a[i] == 'Y')
            v = 1;
        else
            v = -1;
        update(1,1,n,i,v);
    }
    cin>>q;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<get(1,1,n,l,r).a<<'\n';
    }
}

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