Submission #170366

# Submission time Handle Problem Language Result Execution time Memory
170366 2019-12-24T22:19:31 Z rzbt Cake (CEOI14_cake) C++14
0 / 100
1372 ms 33988 KB
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define MAXN 250005
#define F first
#define S second
using namespace std;
typedef long long ll;
ll n,a;
ll niz[MAXN];

ll seg[4*MAXN];
ll lazy[4*MAXN];
set<pair<ll,ll> > svi;


void dodaj(ll l,ll d,ll p,ll x,ll k){
    if(l==d){
        seg[k]=x;
        return;
    }
    ll mid=(l+d)/2;
    if(p<=mid)return dodaj(l,mid,p,x,k+k);
    else dodaj(mid+1,d,p,x,k+k+1);
    seg[k]=max(seg[k+k],seg[k+k+1]);
}
ll dobij(ll l,ll d,ll tl,ll td,ll k){
    if(l>td || d<tl)return 0;
    if(l>=tl && d<=td)return seg[k];
    ll mid=(l+d)/2;
    return max(dobij(l,mid,tl,td,k+k),dobij(mid+1,d,tl,td,k+k+1));
}

void izgradi(ll l,ll d,ll k){
    if(l==d){
        seg[k]=niz[l];
        return;
    }
    ll mid=(l+d)/2;
    izgradi(l,mid,k+k);
    izgradi(mid+1,d,k+k+1);
    seg[k]=max(seg[k+k],seg[k+k+1]);
}

bool nadjen;

ll nadjiL(ll l,ll d,ll tl,ll td,ll k,ll x){
    //printf("   %lld %lld   %lld %lld\n",l,d,tl,td);
    if(nadjen)return -1;
    if(l>td || d<tl)return -1;
    ll mid=(l+d)/2;
    if(l>=tl && d<=td){
        if(l==d ){
            if(seg[k]>x)nadjen=true;
            return (seg[k]>x?l:-1);
        }

        if(seg[k+k+1]>x)return nadjiL(mid+1,d,tl,td,k+k+1,x);
        return nadjiL(l,mid,tl,td,k+k,x);
    }

    ll tren=nadjiL(mid+1,d,tl,td,k+k+1,x);
    if(tren!=-1)return tren;
    return nadjiL(l,mid,tl,td,k+k,x);
}

ll nadjiD(ll l,ll d,ll tl,ll td,ll k,ll x){
    //printf("   %lld %lld   %lld %lld\n",l,d,tl,td);
    if(nadjen)return -1;
    if(l>td || d<tl)return -1;
    ll mid=(l+d)/2;
    if(l>=tl && d<=td){
        if(l==d ){
            //printf("                        %lld %lld\n",seg[k],x);
            if(seg[k]>x)nadjen=true;
            return (seg[k]>x?l:-1);
        }
        //printf("                %lld %lld\n",seg[k+k],x);
        if(seg[k+k]>x)return nadjiD(l,mid,tl,td,k+k,x);
        return nadjiD(mid+1,d,tl,td,k+k+1,x);
    }

    ll tren=nadjiD(l,mid,tl,td,k+k,x);
    if(tren!=-1)return tren;
    return nadjiD(mid+1,d,tl,td,k+k+1,x);
}

int main()///PROMENI U LONG LONG
{
    scanf("%lld %lld", &n, &a);
    for(ll i=1;i<=n;i++){
        scanf("%lld",niz+i);
        niz[i]*=500005;
        svi.insert(mp(niz[i],i));
    }
    izgradi(1,n,1);
    ll qq;
    scanf("%lld", &qq);
    while(qq--){
        char qt[5];
        scanf("%s", qt);
        if(qt[0]=='E'){
            ll koji,postaje;
            scanf("%lld %lld", &koji, &postaje);
            svi.erase(mp(niz[koji],koji));
            //printf("  poz %lld brisem %lld ",koji,niz[koji]);
            auto it=svi.end();
            for(ll i=1;i<postaje;i++){
                it--;
                auto tp=*it;
                tp.F++;
                svi.erase(it);
                it=svi.insert(tp).F;
                dodaj(1,n,tp.second,tp.first,1);
                //printf("%lld ",tp.S);

            }
            it--;
            niz[koji]=(it->first)+1;
            //printf(" stavljam %lld",niz[koji]);
            svi.insert(mp(niz[koji],koji));
            dodaj(1,n,koji,niz[koji],1);
            //printf("     sada %lld\n",dobij(1,n,koji,koji,1));
        }else{
            ll koji;
            scanf("%lld", &koji);
            if(koji==a){
                printf("0\n");
                continue;
            }
            if(koji<a){
                ll najv=dobij(1,n,koji,a-1,1);
                nadjen=false;
                ll tn=nadjiD(1,n,a+1,n,1,najv);
                if(tn==-1)tn=n+1;
                printf("%lld\n",tn-koji-1);
            }else{
                ll najv=dobij(1,n,a+1,koji,1);
                nadjen=false;
                ll tn=nadjiL(1,n,1,a-1,1,najv);
                if(tn==-1)tn=0;
                printf("%lld\n",koji-tn-1);
            }

        }
    }

    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &n, &a);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
cake.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",niz+i);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &qq);
     ~~~~~^~~~~~~~~~~~~
cake.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", qt);
         ~~~~~^~~~~~~~~~
cake.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld %lld", &koji, &postaje);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &koji);
             ~~~~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 716 ms 18156 KB Output isn't correct
2 Incorrect 364 ms 2488 KB Output isn't correct
3 Incorrect 470 ms 8296 KB Output isn't correct
4 Correct 310 ms 1784 KB Output is correct
5 Incorrect 758 ms 18916 KB Output isn't correct
6 Incorrect 600 ms 16896 KB Output isn't correct
7 Incorrect 506 ms 9336 KB Output isn't correct
8 Correct 371 ms 3192 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 10408 KB Output isn't correct
2 Incorrect 119 ms 10232 KB Output isn't correct
3 Incorrect 124 ms 10344 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 333 ms 23160 KB Output isn't correct
6 Incorrect 330 ms 23032 KB Output isn't correct
7 Incorrect 211 ms 23160 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 1912 KB Output isn't correct
2 Incorrect 51 ms 1656 KB Output isn't correct
3 Incorrect 128 ms 5744 KB Output isn't correct
4 Incorrect 159 ms 6008 KB Output isn't correct
5 Incorrect 190 ms 4216 KB Output isn't correct
6 Incorrect 252 ms 7436 KB Output isn't correct
7 Incorrect 203 ms 3576 KB Output isn't correct
8 Incorrect 321 ms 12280 KB Output isn't correct
9 Incorrect 1372 ms 28284 KB Output isn't correct
10 Incorrect 658 ms 12068 KB Output isn't correct
11 Incorrect 854 ms 12900 KB Output isn't correct
12 Incorrect 1319 ms 26588 KB Output isn't correct
13 Incorrect 1059 ms 33988 KB Output isn't correct