답안 #534279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534279 2022-03-08T03:03:03 Z terrasphere 케이크 (CEOI14_cake) C++17
0 / 100
396 ms 14036 KB
#include <bits/stdc++.h>

using namespace std;

long long n,p;
const long long P=1e9;
int q2=1e6,q3=1e6;
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)
        {
            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 query1(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(query1(start,(start+end)/2,left,right,node*2),query1((start+end)/2+1,end,left,right,node*2+1));
}

void query2(int start,int end,int left,int right,int node,long long up)
{
    if(q2!=1e6)
        return;
    if(left>end || start>right)
        return;
    if(left<=start && end<=right)
    {
        if(tree[node]>up)
        {
            if(start==end)
            {
                q2=start;
                return;
            }
            query2(start,(start+end)/2,left,right,node*2,up);
            query2((start+end)/2+1,end,left,right,node*2+1,up);
        }
        return;
    }
    query2(start,(start+end)/2,left,right,node*2,up);
    query2((start+end)/2+1,end,left,right,node*2+1,up);
    return;
}

void query3(int start,int end,int left,int right,int node,long long up)
{
    if(q3!=1e6)
        return;
    if(left>end || start>right)
        return;
    if(left<=start && end<=right)
    {
        if(tree[node]>up)
        {
            if(start==end)
            {
                q3=start;
                return;
            }
            query3((start+end)/2+1,end,left,right,node*2+1,up);
            query3(start,(start+end)/2,left,right,node*2,up);
        }
        return;
    }
    query3((start+end)/2+1,end,left,right,node*2+1,up);
    query3(start,(start+end)/2,left,right,node*2,up);
    return;
}

int main()
{
    int m;
    scanf("%lld%lld",&n,&p);
    tree.resize(4*n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&arr[i]);
        arr[i]*=P;
    }
    init(0,n-1,1);
    scanf("%d",&m);
    for(long long i=1;i<=m;i++)
    {
        q2=1e6;
        q3=1e6;
        char x;
        long long a,b;
        scanf(" %c",&x);
        if(x=='F')
        {
            scanf("%lld",&a);
            long long q;
            int ans=0;
            if(a>p)
            {
                q=query1(0,n-1,p,a-1,1);
                query3(0,n-1,0,p-2,1,q);
                if(q3==1e6)
                    ans=a-1;
                else
                    ans=a-(q3+1)-1;
            }
            else if(a<p)
            {
                q=query1(0,n-1,a-1,p-2,1);
                query2(0,n-1,p,n-1,1,q);
                if(q2==1e6)
                    ans=n-a;
                else
                    ans=q2-a;
            }
            printf("%d\n",ans);
        }
        else
        {
            scanf("%lld%lld",&a,&b);
            arr[a-1]=(n-b+1)*P+i;
            update(0,n-1,1,a-1);
        }
    }
    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%lld%lld",&n,&p);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
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("%d",&m);
      |     ~~~~~^~~~~~~~~
cake.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         scanf(" %c",&x);
      |         ~~~~~^~~~~~~~~~
cake.cpp:121:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |             scanf("%lld",&a);
      |             ~~~~~^~~~~~~~~~~
cake.cpp:146:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |             scanf("%lld%lld",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 149 ms 3016 KB Output isn't correct
2 Correct 145 ms 2988 KB Output is correct
3 Incorrect 145 ms 2996 KB Output isn't correct
4 Correct 135 ms 3012 KB Output is correct
5 Incorrect 171 ms 3748 KB Output isn't correct
6 Incorrect 157 ms 3604 KB Output isn't correct
7 Incorrect 163 ms 3652 KB Output isn't correct
8 Correct 149 ms 3640 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 6052 KB Output isn't correct
2 Incorrect 66 ms 6020 KB Output isn't correct
3 Incorrect 62 ms 5880 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 107 ms 13024 KB Output isn't correct
6 Incorrect 117 ms 13044 KB Output isn't correct
7 Incorrect 78 ms 12916 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 844 KB Output isn't correct
2 Incorrect 25 ms 964 KB Output isn't correct
3 Incorrect 48 ms 3268 KB Output isn't correct
4 Incorrect 45 ms 3272 KB Output isn't correct
5 Incorrect 66 ms 1788 KB Output isn't correct
6 Incorrect 90 ms 4936 KB Output isn't correct
7 Incorrect 91 ms 2756 KB Output isn't correct
8 Incorrect 79 ms 6604 KB Output isn't correct
9 Incorrect 377 ms 13940 KB Output isn't correct
10 Incorrect 240 ms 3868 KB Output isn't correct
11 Incorrect 234 ms 4656 KB Output isn't correct
12 Incorrect 396 ms 12020 KB Output isn't correct
13 Incorrect 355 ms 14036 KB Output isn't correct