oj.uz

답안 #535115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535115 2022-03-09T12:56:43 Z terrasphere 케이크 (CEOI14_cake) C++17
20 / 100
 2000 ms 10652 KB 
#include <bits/stdc++.h>

using namespace std;

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

long long arr[252525];

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)
    {
        if(start==end)
        {
            tree[node]=arr[start];
            return;
        }
    }
    update(start,(start+end)/2,node*2,index);
    update((start+end)/2+1,end,node*2+1,index);
    tree[node]=max(tree[node*2],tree[node*2+1]);
    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]);
    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);
            long long pre=arr[a];
            for(int i=0;i<N;i++)
            {
                if(arr[i]>pre && arr[i]<=N-b+1)
                {
                    arr[i]--;
                    update(0,N-1,1,i);
                }
            }
            arr[a]=N-b+1;
            update(0,N-1,1,a);
        }
        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:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%lld%lld",&N,&A);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         scanf("%lld",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%lld",&Q);
      |     ~~~~~^~~~~~~~~~~
cake.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf(" %c",&type);
      |         ~~~~~^~~~~~~~~~~~~
cake.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         scanf("%lld",&a);
      |         ~~~~~^~~~~~~~~~~
cake.cpp:124:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |             scanf("%lld",&b);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 121 ms 376 KB Output is correct
5 Execution timed out 2087 ms 824 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2072 ms 708 KB Time limit exceeded
2 Execution timed out 2070 ms 588 KB Time limit exceeded
3 Execution timed out 2084 ms 680 KB Time limit exceeded
4 Execution timed out 2079 ms 588 KB Time limit exceeded
5 Execution timed out 2071 ms 1148 KB Time limit exceeded
6 Execution timed out 2090 ms 1348 KB Time limit exceeded
7 Execution timed out 2076 ms 1268 KB Time limit exceeded
8 Execution timed out 2076 ms 1228 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 914 ms 4852 KB Output is correct
2 Correct 416 ms 4608 KB Output is correct
3 Correct 153 ms 4508 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1672 ms 10652 KB Output is correct
6 Correct 956 ms 10652 KB Output is correct
7 Correct 83 ms 10408 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2074 ms 672 KB Time limit exceeded
2 Execution timed out 2078 ms 756 KB Time limit exceeded
3 Execution timed out 2079 ms 2252 KB Time limit exceeded
4 Execution timed out 2085 ms 2252 KB Time limit exceeded
5 Execution timed out 2080 ms 556 KB Time limit exceeded
6 Execution timed out 2088 ms 2764 KB Time limit exceeded
7 Execution timed out 2077 ms 816 KB Time limit exceeded
8 Execution timed out 2072 ms 4200 KB Time limit exceeded
9 Execution timed out 2072 ms 10000 KB Time limit exceeded
10 Execution timed out 2075 ms 532 KB Time limit exceeded
11 Execution timed out 2076 ms 1096 KB Time limit exceeded
12 Execution timed out 2066 ms 8004 KB Time limit exceeded
13 Execution timed out 2079 ms 10060 KB Time limit exceeded