Submission #709597

#	Time	Username	Problem	Language	Result	Execution time	Memory
709597		ToroTN	Growing Trees (BOI11_grow)	C++14	100 / 100	118 ms	3284 KiB

grow

#include<bits/stdc++.h>
using namespace std;
int n,t,a[100005],x,y,fen[100005],st,md,ed,l,r;
char op[5];
void update(int u,int val)
{
    while(u<=n)
    {
        fen[u]+=val;
        u+=(u&(-u));
    }
}
int query(int u)
{
    int cnt=0;
    while(u>0)
    {
        cnt+=fen[u];
        u-=(u&(-u));
    }
    return cnt;
}
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)update(i,a[i]-a[i-1]);
    /*for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");*/
    while(t--)
    {
        scanf("%s",op);
        if(op[0]=='C')
        {
            scanf("%d%d",&x,&y);
        }else
        {
            scanf("%d%d",&y,&x);
        }
        if(op[0]=='C')
        {
            st=1,ed=n;
            while(ed>=st)
            {
                md=(st+ed)/2;
                if(query(md)<x)
                {
                    st=md+1;
                }else
                {
                    ed=md-1;
                }
            }
            l=st;
            if(l>n)
            {
                printf("0\n");
                continue;
            }
            st=1,ed=n;
            while(ed>=st)
            {
                md=(st+ed)/2;
                if(query(md)>y)
                {
                    ed=md-1;
                }else
                {
                    st=md+1;
                }
            }
            r=ed;
            printf("%d\n",r-l+1);
        }else
        {
            st=1,ed=n;
            while(ed>=st)
            {
                md=(st+ed)/2;
                if(query(md)<x)
                {
                    st=md+1;
                }else
                {
                    ed=md-1;
                }
            }
            l=st;
            //printf("%d ",l);
            r=l+y-1;
            //printf("%d\n",r);
            if(r>=n)
            {
                update(l,1);
            }else
            {
                int numr=query(r);
                st=1,ed=n;
                while(ed>=st)
                {
                    md=(st+ed)/2;
                    if(query(md)>=numr)
                    {
                        ed=md-1;
                    }else
                    {
                        st=md+1;
                    }
                }
                int pos_l=ed;
                /*printf("%d\n",r);
                printf("%d %d %d\n",st,md,ed);
                break;*/
                if(l<=pos_l)
                {
                    update(l,1);
                    update(pos_l+1,-1);
                }
                int remain=y-(pos_l-l+1);
                int lst;
                st=1,ed=n;
                while(ed>=st)
                {
                    md=(st+ed)/2;
                    if(query(md)>numr)
                    {
                        ed=md-1;
                    }else
                    {
                        st=md+1;
                    }
                }
                lst=ed;
                update(lst-remain+1,1);
                update(lst+1,-1);
                /*for(int i=1;i<=n;i++)
                {
                    printf("%d ",query(i));
                }
                printf("\n");*/
            }
        }   
    }
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d%d",&n,&t);
      |     ~~~~~^~~~~~~~~~~~~~
grow.cpp:26:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
grow.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%s",op);
      |         ~~~~~^~~~~~~~~
grow.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |             scanf("%d%d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~
grow.cpp:42:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |             scanf("%d%d",&y,&x);
      |             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10