제출 #708844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708844		ktkerem	케이크 (CEOI14_cake)	C++17	0 / 100	1895 ms	27848 KiB

cake

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e18+7;
const ll sus = 1e6;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll a , ll b){
    return (rng() % (b-a+1)) + a;
}
/*global variables*/
ll n , k;
std::vector<llll> ar;
llll gt[11];
std::vector<llll> valt;
/**/
/*functions*/
void upd(ll nt , ll vl , ll l = 0 , ll r = n-1 , ll a = 1){
    //std::cout << l << " " << r << std::endl;
    if(l == r){
        valt[a] = {vl , vl};
        return;
    }
    ll md = (l + r)/2;
    if(nt <= md){
        upd(nt , vl , l , md , a*2);
    }
    else{
        upd(nt , vl , md+1 , r , a*2+1);
    }
    valt[a] = {std::min(valt[a*2].fi , valt[a*2+1].fi) , std::max(valt[a*2].sec , valt[a*2+1].sec)};
}
llll que(ll l , ll r , ll nl = 0 , ll nr = n-1 , ll a = 1){
    if(nl > r || nr < l){
        return{limit , -limit};
    }
    if(l <= nl && r >= nr){
        return valt[a];
    }
    ll md=(nl + nr)/2;
    llll lf = que(l , r , nl , md , a*2);
    llll rg = que(l , r , md+1 , nr , a*2+1);
    return {std::min(lf.fi , rg.fi) , std::max(lf.sec , rg.sec)};
}
/**/
void solve(){
    std::cin >> n >> k;k--;
    valt.resize(4 * n + 5);
    ll pl = std::min(n , 10ll);
    ar.resize(n);
    for(ll i = 0;n>i;i++){
        std::cin >> ar[i].fi;
        ar[i].sec = i;
        if(i == k){
            ar[i].fi = 0;   
        }
        upd(i , ar[i].fi);
    }
    std::sort(all(ar) , std::greater<llll>());
    for(ll i=0;pl>i;i++){
        gt[i] = ar[i];
    }
    ll q;std::cin >> q;
    while(q--){
        std::string h;ll x;std::cin >> h >> x;x--;
        if(h == "E"){
            ll y;std::cin >> y;
            y--;
            if(x == k){
                continue;
            }
            ll kd = 0;
            for(ll i = 0;pl>i;i++){
                if(gt[i].sec == x){
                    kd = 1;
                }
                if(kd){
                    gt[i] = gt[i+1];
                }
            }
            /*for(ll i = 0;pl>i;i++){
                std::cout << gt[i].fi <<  " " << gt[i].sec << "\n";
            }*/
            //std::cout << "\n\n";
            for(ll i = pl;i >= y;i--){
                gt[i+1] = gt[i];
            }
            gt[y].sec = x;
            for(ll i = 0;y>=i;i++){
                gt[i].fi++;
                upd(gt[i].sec , gt[i].fi);
            }
            /*for(ll i = 0;pl>i;i++){
                std::cout << gt[i].fi <<  " " << gt[i].sec << "\n";
            }*/
        }
        else{
            if(k > x){
                llll o = que(x , k);
                //std::cout << o.fi << " " << o.sec << "\n";
                ll l = k , r = n-1;
                while(r > l){
                    ll md = (l + r + 1)/2;
                    llll sl = que(k , md);
                    //std::cout << k << " " << md << " " << sl.fi << " " << sl.sec << "\n";
                    if(o.sec < sl.sec){
                        r = md-1;
                    }
                    else{
                        l = md;
                    }
                }
                std::cout << l - k + k - x << "\n"; 
            }
            else if(k < x){
                llll o = que(k , x);
                ll l = 0 , r = k;
                while(r > l){
                    ll md = (l + r)/2;
                    llll sl = que(md , k);
                    if(o.sec < sl.sec){
                        l = md + 1;
                    }
                    else{
                        r = md;
                    }
                }
                std::cout << k - l + x - k << "\n";
            }
            else{
                std::cout << "0\n";
            }
        }
    }
    return;/**/
}
int main(){
    /*std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("in.txt" , "r" , stdin);
        freopen("out.txt" , "w" , stdout);
    #endif*/
    ll t = 1;
    //std::cin >> t;
    while(t--){
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

cake.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50