답안 #535097

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

using namespace std;

long long N,Q,A;
int index1,index2;
const long long P=1e9;

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(start<=index && index<=end)
    {
        tree[node]=max(tree[node],arr[index]);
        if(start==end)
            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!=-1)
        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!=-1)
        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]);
        arr[i]*=P;
    }
    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);
            arr[a]=(N-b+1)*P+t;
            update(0,N-1,1,a);
        }
        else
        {
            index1=-1;
            index2=-1;
            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);
                if(index1!=-1)
                    answer=index1-a;
                else
                    answer=N-a;
                answer--;
            }
            else
            {
                cur_max=maximum(0,N-1,A+1,a,1);
                maximum_index2(0,N-1,0,A-1,1,cur_max);
                if(index2!=-1)
                    answer=a-index2;
                else
                    answer=a-1;
                answer--;
            }
            printf("%d\n",answer);
        }
    }
    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     scanf("%lld%lld",&N,&A);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
cake.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%lld",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     scanf("%lld",&Q);
      |     ~~~~~^~~~~~~~~~~
cake.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         scanf(" %c",&type);
      |         ~~~~~^~~~~~~~~~~~~
cake.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         scanf("%lld",&a);
      |         ~~~~~^~~~~~~~~~~
cake.cpp:123:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |             scanf("%lld",&b);
      |             ~~~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 142 ms 588 KB Output isn't correct
2 Incorrect 137 ms 588 KB Output isn't correct
3 Incorrect 139 ms 588 KB Output isn't correct
4 Incorrect 137 ms 588 KB Output isn't correct
5 Incorrect 150 ms 1228 KB Output isn't correct
6 Incorrect 155 ms 1228 KB Output isn't correct
7 Incorrect 150 ms 1228 KB Output isn't correct
8 Incorrect 147 ms 1228 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 4676 KB Output isn't correct
2 Incorrect 68 ms 4580 KB Output isn't correct
3 Incorrect 58 ms 4556 KB Output isn't correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Incorrect 102 ms 10656 KB Output isn't correct
6 Incorrect 99 ms 10712 KB Output isn't correct
7 Incorrect 74 ms 10436 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 460 KB Output isn't correct
2 Incorrect 26 ms 612 KB Output isn't correct
3 Incorrect 50 ms 2396 KB Output isn't correct
4 Incorrect 47 ms 2444 KB Output isn't correct
5 Incorrect 63 ms 604 KB Output isn't correct
6 Incorrect 91 ms 3268 KB Output isn't correct
7 Incorrect 93 ms 1120 KB Output isn't correct
8 Incorrect 73 ms 4212 KB Output isn't correct
9 Incorrect 339 ms 11652 KB Output isn't correct
10 Incorrect 207 ms 1388 KB Output isn't correct
11 Incorrect 233 ms 2372 KB Output isn't correct
12 Incorrect 318 ms 9724 KB Output isn't correct
13 Incorrect 311 ms 11812 KB Output isn't correct