Submission #534285

# Submission time Handle Problem Language Result Execution time Memory
534285 2022-03-08T03:08:01 Z terrasphere Cake (CEOI14_cake) C++17
0 / 100
354 ms 11708 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)
            {
                //q3+1~a
                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)
            {
                //a~q2-1
                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-1-a+1;
            }
            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:148:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |             scanf("%lld%lld",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory 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 -
# Verdict Execution time Memory Grader output
1 Incorrect 173 ms 588 KB Output isn't correct
2 Correct 140 ms 588 KB Output is correct
3 Incorrect 141 ms 588 KB Output isn't correct
4 Correct 131 ms 588 KB Output is correct
5 Incorrect 162 ms 1228 KB Output isn't correct
6 Incorrect 159 ms 1228 KB Output isn't correct
7 Incorrect 146 ms 1228 KB Output isn't correct
8 Correct 153 ms 1240 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 4676 KB Output isn't correct
2 Incorrect 77 ms 4596 KB Output isn't correct
3 Incorrect 57 ms 4576 KB Output isn't correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Incorrect 107 ms 10652 KB Output isn't correct
6 Incorrect 96 ms 10712 KB Output isn't correct
7 Incorrect 74 ms 10504 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 460 KB Output isn't correct
2 Incorrect 24 ms 592 KB Output isn't correct
3 Incorrect 47 ms 2364 KB Output isn't correct
4 Incorrect 48 ms 2516 KB Output isn't correct
5 Incorrect 74 ms 580 KB Output isn't correct
6 Incorrect 91 ms 3212 KB Output isn't correct
7 Incorrect 84 ms 1068 KB Output isn't correct
8 Incorrect 77 ms 4212 KB Output isn't correct
9 Incorrect 354 ms 11688 KB Output isn't correct
10 Incorrect 210 ms 1464 KB Output isn't correct
11 Incorrect 252 ms 2412 KB Output isn't correct
12 Incorrect 338 ms 9704 KB Output isn't correct
13 Incorrect 331 ms 11708 KB Output isn't correct