답안 #535098

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535098 2022-03-09T12:04:05 Z terrasphere 케이크 (CEOI14_cake) C++17
0 / 100
381 ms 11740 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-1;
                else
                    answer=N-a-1;
            }
            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-1;
                else
                    answer=a-2;
            }
            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 160 ms 588 KB Output isn't correct
2 Incorrect 159 ms 588 KB Output isn't correct
3 Incorrect 188 ms 588 KB Output isn't correct
4 Incorrect 148 ms 588 KB Output isn't correct
5 Incorrect 176 ms 1228 KB Output isn't correct
6 Incorrect 166 ms 1228 KB Output isn't correct
7 Incorrect 188 ms 1228 KB Output isn't correct
8 Incorrect 182 ms 1228 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 108 ms 4788 KB Output isn't correct
2 Incorrect 68 ms 4548 KB Output isn't correct
3 Incorrect 81 ms 4620 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 152 ms 10692 KB Output isn't correct
6 Incorrect 114 ms 10680 KB Output isn't correct
7 Incorrect 75 ms 10408 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 464 KB Output isn't correct
2 Incorrect 41 ms 588 KB Output isn't correct
3 Incorrect 58 ms 2428 KB Output isn't correct
4 Incorrect 62 ms 2432 KB Output isn't correct
5 Incorrect 70 ms 592 KB Output isn't correct
6 Incorrect 93 ms 3348 KB Output isn't correct
7 Incorrect 110 ms 1100 KB Output isn't correct
8 Incorrect 80 ms 4172 KB Output isn't correct
9 Incorrect 381 ms 11720 KB Output isn't correct
10 Incorrect 245 ms 1444 KB Output isn't correct
11 Incorrect 246 ms 2424 KB Output isn't correct
12 Incorrect 361 ms 9740 KB Output isn't correct
13 Incorrect 308 ms 11740 KB Output isn't correct