oj.uz

Submission #535138

# Submission time Handle Problem Language Result Execution time Memory
535138 2022-03-09T13:30:30 Z terrasphere Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 13524 KB 
#include <bits/stdc++.h>

using namespace std;

long long N,Q,A;
int index1,index2;

long long arr[252525];

long long top[11];
long long top_index[11];

vector<long long> tree;

void init(int start,int end,int node)
{
    if(start==end)
    {
        tree[node]=arr[start];
        return;
    }
    init(start,(start+end)/2,node*2);
    init((start+end)/2+1,end,node*2+1);
    tree[node]=max(tree[node*2],tree[node*2+1]);
    return;
}

void update(int start,int end,int node,int index)
{
    if(index<start || end<index)
        return;
    if(start<=index && index<=end)
    {
        tree[node]=max(tree[node],arr[index]);
        if(start==end)
        {
            tree[node]=arr[index];
            return;
        }
        update(start,(start+end)/2,node*2,index);
        update((start+end)/2+1,end,node*2+1,index);
    }
    return;
}

long long maximum(int start,int end,int left,int right,int node)
{
    if(start>right || end<left)
        return 0;
    if(left<=start && end<=right)
        return tree[node];
    return max(maximum(start,(start+end)/2,left,right,node*2),maximum((start+end)/2+1,end,left,right,node*2+1));
}

void maximum_index1(int start,int end,int left,int right,int node,long long point)
{
    if(index1!=1e6)
        return;
    if(right<start || end<left)
        return;
    if(left<=start && end<=right)
    {
        if(tree[node]>point)
        {
            if(start==end)
            {
                index1=start;
                return;
            }
            maximum_index1(start,(start+end)/2,left,right,node*2,point);
            maximum_index1((start+end)/2+1,end,left,right,node*2+1,point);
        }
        else
            return;
    }
    maximum_index1(start,(start+end)/2,left,right,node*2,point);
    maximum_index1((start+end)/2+1,end,left,right,node*2+1,point);
    return;
}

void maximum_index2(int start,int end,int left,int right,int node,long long point)
{
    if(index2!=-1e6)
        return;
    if(right<start || end<left)
        return;
    if(left<=start && end<=right)
    {
        if(tree[node]>point)
        {
            if(start==end)
            {
                index2=start;
                return;
            }
            maximum_index2((start+end)/2+1,end,left,right,node*2+1,point);
            maximum_index2(start,(start+end)/2,left,right,node*2,point);
        }
        else
            return;
    }
    maximum_index2((start+end)/2+1,end,left,right,node*2+1,point);
    maximum_index2(start,(start+end)/2,left,right,node*2,point);
    return;
}

int main()
{
    scanf("%lld%lld",&N,&A);
    A--;
    tree.resize(4*N);
    for(int i=0;i<N;i++)
    {
        scanf("%lld",&arr[i]);
        if(arr[i]>N-10)
        {
            top[N-arr[i]+1]=arr[i];
            top_index[N-arr[i]+1]=i;
        }
    }
    init(0,N-1,1);
    scanf("%lld",&Q);
    for(long long t=1;t<=Q;t++)
    {
        char type;
        scanf(" %c",&type);
        long long a,b;
        scanf("%lld",&a);
        a--;
        int answer;
        long long cur_max;
        if(type=='E')
        {
            scanf("%lld",&b);
            for(int i=min(10,(int)N);i<b;i--)
            {
                top_index[i]=top_index[i+1];
                top[i]=top[i+1];
            }
            top_index[b]=a;
            top[b]++;
            arr[a]=top[b];
            update(0,N-1,1,a);
            for(int i=b-1;i>=1;i--)
            {
                top[i]++;
                arr[top_index[i]]=top[i];
                update(0,N-1,1,top_index[i]);
            }
        }
        else
        {
            index1=1e6;
            index2=-1e6;
            if(A==0 || A==N-1)
                answer=abs(A-a);
            else if(A==a)
                answer=0;
            else if(A>a)
            {
                cur_max=maximum(0,N-1,a,A-1,1);
                maximum_index1(0,N-1,A+1,N-1,1,cur_max);
                index1=min((int)N,index1);
                answer=index1-a-1;
                //printf("%d %d %d %d\n",answer,a,A,index1);
            }
            else
            {
                cur_max=maximum(0,N-1,A+1,a,1);
                maximum_index2(0,N-1,0,A-1,1,cur_max);
                index2=max(-1,index2);
                answer=a-index2-1;
                //printf("%d %d %d %d\n",answer,index2,A,a);
            }
            printf("%d\n",answer);
        }
        //for(int i=0;i<N;i++)
        //    printf("%d %lld\n",i+1,arr[i]);
    }
    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%lld%lld",&N,&A);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         scanf("%lld",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     scanf("%lld",&Q);
      |     ~~~~~^~~~~~~~~~~
cake.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf(" %c",&type);
      |         ~~~~~^~~~~~~~~~~~~
cake.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf("%lld",&a);
      |         ~~~~~^~~~~~~~~~~
cake.cpp:134:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |             scanf("%lld",&b);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 2600 KB Output isn't correct
2 Correct 192 ms 2584 KB Output is correct
3 Incorrect 195 ms 2448 KB Output isn't correct
4 Correct 146 ms 2516 KB Output is correct
5 Incorrect 290 ms 3096 KB Output isn't correct
6 Incorrect 242 ms 3020 KB Output isn't correct
7 Incorrect 226 ms 3020 KB Output isn't correct
8 Correct 151 ms 3120 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 5728 KB Output isn't correct
2 Incorrect 76 ms 5492 KB Output isn't correct
3 Incorrect 61 ms 5516 KB Output isn't correct
4 Incorrect 0 ms 304 KB Output isn't correct
5 Incorrect 122 ms 12488 KB Output isn't correct
6 Incorrect 1631 ms 12628 KB Output isn't correct
7 Incorrect 78 ms 12356 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 864 KB Output isn't correct
2 Incorrect 40 ms 944 KB Output isn't correct
3 Incorrect 62 ms 3324 KB Output isn't correct
4 Incorrect 65 ms 3248 KB Output isn't correct
5 Incorrect 94 ms 1456 KB Output isn't correct
6 Incorrect 109 ms 4332 KB Output isn't correct
7 Incorrect 110 ms 2200 KB Output isn't correct
8 Incorrect 108 ms 6084 KB Output isn't correct
9 Incorrect 509 ms 13524 KB Output isn't correct
10 Incorrect 322 ms 3340 KB Output isn't correct
11 Incorrect 369 ms 4224 KB Output isn't correct
12 Incorrect 512 ms 11552 KB Output isn't correct
13 Execution timed out 2003 ms 11120 KB Time limit exceeded