Submission #1349143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1349143		Muhammad_Aneeq	Cake (CEOI14_cake)	C++20	0 / 100	448 ms	26536 KiB

cake

#include <bits/stdc++.h>
using namespace std;
int const N=1e6;
struct node
{
    int la=0,ls=-1,mx=0;
};
struct seg
{
    node arr[N]={};
    void push(int i)
    {
        for (int j=2*i;j<=2*i+1;j++)
        {
            if (arr[i].ls!=-1)
            {
                arr[j].mx=arr[j].ls=arr[i].ls;
                arr[j].la=0;
            }
            arr[j].mx+=arr[i].la;
            arr[j].la+=arr[i].la;
        }
        arr[i].la=0;
        arr[i].ls=-1;
    }
    void upd(int i,int st,int en,int l,int r,int vl)
    {
        if (st>=l&&en<=r)
        {
            arr[i].la+=vl;
            arr[i].mx+=vl;
            return;
        }
        if (st>r||en<l)
            return;
        int mid=(st+en)/2;
        push(i);
        upd(i*2,st,mid,l,r,vl);
        upd(i*2+1,mid+1,en,l,r,vl);
        arr[i].mx=max(arr[i*2].mx,arr[i*2+1].mx);
    }
    void update(int i,int st,int en,int l,int r,int vl)
    {
        if (st>=l&&en<=r)
        {
            arr[i].ls=vl;
            arr[i].mx=vl;
            arr[i].la=0;
            return;
        }
        if (st>r||en<l)
            return;
        int mid=(st+en)/2;
        push(i);
        update(i*2,st,mid,l,r,vl);
        update(i*2+1,mid+1,en,l,r,vl);
        arr[i].mx=max(arr[i*2].mx,arr[i*2+1].mx);
    }
    int get(int i,int r,int st,int en)
    {
        if (st==en)
            return arr[i].mx;
        int mid=(st+en)/2;
        push(i);
        if (r<=mid)
            return get(i*2,r,st,mid);
        return get(i*2+1,r,mid+1,en);
    }
};
void solve()
{
    // exit(0);
    // cerr<<1<<endl;
    int n,a;
    cin>>n>>a;
    int vl[n]={};
    for (int i=0;i<n;i++)
        cin>>vl[i];
    if (a==1||a==n)
    {
        int q;
        cin>>q;
        while (q--)
        {
            char ty;
            cin>>ty;
            if (ty=='F')
            {   
                int b;
                cin>>b;
                cout<<abs(a-b)<<endl;
            }
            else
            {
                int i,e;
                cin>>i>>e;
            }
        }
        return;
    }
    int sz[2]={};
    sz[0]=a-2;
    sz[1]=n-a-1;
    int mx=0;
    seg ST[2]={};
    for (int i=a-2;i>=0;i--)
    {
        mx=max(mx,vl[i]);
        ST[0].update(1,0,sz[0],a-2-i,a-2-i,mx);
    }
    mx=0;
    for (int i=a;i<n;i++)
    {
        mx=max(mx,vl[i]);
        ST[1].update(1,0,sz[1],i-a,i-a,mx);
    }
    int q;
    cin>>q;
    while (q--)
    {
        char ty;
        cin>>ty;
        if (ty=='F')
        {
            int b;
            cin>>b;
            if (b<a)
            {
                int vl=ST[0].get(1,a-b-1,0,sz[0]);
                int st=-1,en=sz[1]+1;
                while (st+1<en)
                {
                    int mid=(st+en)/2;
                    if (ST[1].get(1,mid,0,sz[1])>vl)
                        en=mid;
                    else
                        st=mid;
                }
                cout<<st+1+a-b<<endl;
            }
            else if (b>a)
            {
                int vl=ST[1].get(1,b-a-1,0,sz[1]);
                int st=-1,en=sz[0]+1;
                while (st+1<en)
                {
                    int mid=(st+en)/2;
                    if (ST[0].get(1,mid,0,sz[0])>vl)
                        en=mid;
                    else
                        st=mid;
                }
                cout<<st+1+b-a<<endl;
            }
            else
                cout<<0<<endl;
        }
        else
        {
            int i,f;
            cin>>i>>f;
            f=n-f+1;
            if (i<a)
            {
                int vl=ST[0].get(1,a-i-1,0,sz[0]);
                if (vl>=f) continue;
                int st=-1,en=sz[1]+1;
                while (st+1<en)
                {
                    int mid=(st+en)/2;
                    if (ST[1].get(1,mid,0,sz[1])<vl)
                        st=mid;
                    else
                        en=mid;
                }
                int l=st+1;
                st=-1,en=sz[1]+1;
                while (st+1<en)
                {
                    int mid=(st+en)/2;
                    if (ST[1].get(1,mid,0,sz[1])>=f)
                        en=mid;
                    else
                        st=mid;
                }
                int r=en-1;
                ST[1].upd(1,0,sz[1],l,r,-1);
                st=abs(i-a)-1,en=sz[0]+1;
                while (st+1<en)
                {
                    int mid=(st+en)/2;
                    if (ST[0].get(1,mid,0,sz[0])<f)
                        st=mid;
                    else
                        en=mid;
                }
                ST[0].update(1,0,sz[0],abs(i-a)-1,st,f);
            }
            else if (i>a)
            {
                int vl=ST[1].get(1,i-a-1,0,sz[1]);
                if (vl>=f) continue;
                int st=-1,en=sz[0]+1;
                while (st+1<en)
                {
                    int mid=(st+en)/2;
                    if (ST[0].get(1,mid,0,sz[0])<vl)
                        st=mid;
                    else
                        en=mid;
                }
                int l=st+1;
                st=-1,en=sz[0]+1;
                while (st+1<en)
                {
                    int mid=(st+en)/2;
                    if (ST[0].get(1,mid,0,sz[0])>=f)
                        en=mid;
                    else
                        st=mid;
                }
                int r=en-1;
                ST[0].upd(1,0,sz[0],l,r,-1);
                st=abs(i-a)-1,en=sz[1]+1;
                while (st+1<en)
                {
                    int mid=(st+en)/2;
                    if (ST[1].get(1,mid,0,sz[1])<f)
                        st=mid;
                    else
                        en=mid;
                }
                ST[1].update(1,0,sz[1],abs(i-a)-1,st,f);
            }
            else
                continue;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50