oj.uz

Submission #535149

# Submission time Handle Problem Language Result Execution time Memory
535149 2022-03-09T14:03:14 Z terrasphere Cake (CEOI14_cake) C++17
100 / 100
 543 ms 13832 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--)
            {
                if(arr[a]>arr[top_index[i]])
                    continue;
                top_index[i]=top_index[i-1];
                top[i]=top[i-1];
            }
            top_index[b]=a;
            for(int i=b;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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 9 ms 844 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 1916 KB Output is correct
2 Correct 198 ms 1972 KB Output is correct
3 Correct 225 ms 1880 KB Output is correct
4 Correct 155 ms 1972 KB Output is correct
5 Correct 325 ms 2672 KB Output is correct
6 Correct 300 ms 2484 KB Output is correct
7 Correct 225 ms 2460 KB Output is correct
8 Correct 180 ms 2524 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 5444 KB Output is correct
2 Correct 77 ms 5400 KB Output is correct
3 Correct 62 ms 5236 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 102 ms 11460 KB Output is correct
6 Correct 113 ms 11584 KB Output is correct
7 Correct 76 ms 11184 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 844 KB Output is correct
2 Correct 32 ms 1012 KB Output is correct
3 Correct 70 ms 3024 KB Output is correct
4 Correct 69 ms 3104 KB Output is correct
5 Correct 96 ms 1340 KB Output is correct
6 Correct 113 ms 4020 KB Output is correct
7 Correct 121 ms 1856 KB Output is correct
8 Correct 105 ms 5020 KB Output is correct
9 Correct 543 ms 13064 KB Output is correct
10 Correct 352 ms 2904 KB Output is correct
11 Correct 382 ms 3724 KB Output is correct
12 Correct 502 ms 10916 KB Output is correct
13 Correct 491 ms 13832 KB Output is correct