답안 #535108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535108 2022-03-09T12:31:12 Z terrasphere 케이크 (CEOI14_cake) C++17
0 / 100
355 ms 11920 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!=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]);
        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=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);
        }
    }
    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 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 150 ms 588 KB Output isn't correct
2 Correct 143 ms 588 KB Output is correct
3 Incorrect 150 ms 588 KB Output isn't correct
4 Correct 159 ms 588 KB Output is correct
5 Incorrect 159 ms 1228 KB Output isn't correct
6 Incorrect 150 ms 1228 KB Output isn't correct
7 Incorrect 150 ms 1228 KB Output isn't correct
8 Correct 147 ms 1228 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 94 ms 4752 KB Output isn't correct
2 Incorrect 65 ms 4628 KB Output isn't correct
3 Incorrect 57 ms 4536 KB Output isn't correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 99 ms 10628 KB Output isn't correct
6 Incorrect 99 ms 10688 KB Output isn't correct
7 Incorrect 74 ms 10436 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 500 KB Output isn't correct
2 Incorrect 28 ms 592 KB Output isn't correct
3 Incorrect 50 ms 2412 KB Output isn't correct
4 Incorrect 45 ms 2452 KB Output isn't correct
5 Incorrect 61 ms 612 KB Output isn't correct
6 Incorrect 87 ms 3220 KB Output isn't correct
7 Incorrect 86 ms 1092 KB Output isn't correct
8 Incorrect 78 ms 4308 KB Output isn't correct
9 Incorrect 355 ms 11596 KB Output isn't correct
10 Incorrect 201 ms 1392 KB Output isn't correct
11 Incorrect 235 ms 2332 KB Output isn't correct
12 Incorrect 321 ms 9696 KB Output isn't correct
13 Incorrect 305 ms 11920 KB Output isn't correct