답안 #534219

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534219 2022-03-08T02:28:11 Z terrasphere 케이크 (CEOI14_cake) C++17
0 / 100
374 ms 17960 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 204 KB Output is correct
2 Incorrect 1 ms 300 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 141 ms 4980 KB Output isn't correct
2 Correct 152 ms 5020 KB Output is correct
3 Incorrect 133 ms 5028 KB Output isn't correct
4 Correct 132 ms 5024 KB Output is correct
5 Incorrect 166 ms 5940 KB Output isn't correct
6 Incorrect 151 ms 6340 KB Output isn't correct
7 Incorrect 145 ms 5996 KB Output isn't correct
8 Correct 146 ms 6320 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 6020 KB Output isn't correct
2 Incorrect 74 ms 6020 KB Output isn't correct
3 Incorrect 57 ms 5956 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 153 ms 13096 KB Output isn't correct
6 Incorrect 106 ms 13140 KB Output isn't correct
7 Incorrect 95 ms 12864 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 836 KB Output isn't correct
2 Incorrect 27 ms 964 KB Output isn't correct
3 Incorrect 52 ms 3308 KB Output isn't correct
4 Incorrect 65 ms 3348 KB Output isn't correct
5 Incorrect 63 ms 1724 KB Output isn't correct
6 Incorrect 96 ms 4904 KB Output isn't correct
7 Incorrect 102 ms 2732 KB Output isn't correct
8 Incorrect 80 ms 6620 KB Output isn't correct
9 Incorrect 350 ms 17884 KB Output isn't correct
10 Incorrect 228 ms 5072 KB Output isn't correct
11 Incorrect 238 ms 6700 KB Output isn't correct
12 Incorrect 374 ms 15552 KB Output isn't correct
13 Incorrect 347 ms 17960 KB Output isn't correct