oj.uz

Submission #709597

# Submission time Handle Problem Language Result Execution time Memory
709597 2023-03-14T01:39:20 Z ToroTN Growing Trees (BOI11_grow) C++14
100 / 100
 118 ms 3284 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2268 KB Output is correct
2 Correct 117 ms 2696 KB Output is correct
3 Correct 56 ms 2648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 60 ms 1332 KB Output is correct
6 Correct 67 ms 1612 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 41 ms 1140 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1588 KB Output is correct
2 Correct 61 ms 1748 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 49 ms 1428 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1848 KB Output is correct
2 Correct 71 ms 1644 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 61 ms 1692 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2000 KB Output is correct
2 Correct 101 ms 2212 KB Output is correct
3 Correct 18 ms 836 KB Output is correct
4 Correct 36 ms 2240 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1936 KB Output is correct
2 Correct 101 ms 2248 KB Output is correct
3 Correct 56 ms 2492 KB Output is correct
4 Correct 23 ms 784 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2124 KB Output is correct
2 Correct 73 ms 2268 KB Output is correct
3 Correct 41 ms 2580 KB Output is correct
4 Correct 18 ms 796 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 2612 KB Output is correct
2 Correct 107 ms 2248 KB Output is correct
3 Correct 27 ms 1740 KB Output is correct
4 Correct 67 ms 2168 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 2544 KB Output is correct
2 Correct 118 ms 2644 KB Output is correct
3 Correct 105 ms 2848 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 3284 KB Output is correct