제출 #709221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
709221		ktkerem	케이크 (CEOI14_cake)	C++17	0 / 100	2083 ms	13080 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[15];
struct segt{
    std::vector<ll> valt;
    void upd(ll l , ll r , ll nt , ll a , ll vl){
        if(l == r){
            //std::cout << l << " " << r << " " << a << std::endl;
            valt[a] = vl;
            return ;
        }
        ll md = (l + r)/2;
        if(nt <= md){
            upd(l , md , nt , a*2 , vl);
        }
        else{
            upd(md+1 , r , nt , a*2+1 , vl);
        }
        valt[a] = std::max(valt[a*2] , valt[a*2+1]);
    }
    ll que(ll l , ll r , ll nl , ll nr , ll a){
        if(nl > r || nr < l){
            return 0;
        }
        if(nl >= l && nr <= r){
            return valt[a];
        }
        ll md = (nl + nr)/2;
        ll lf = que(l , r , nl , md , a*2) , rg = que(l , r , md+1 , nr , a*2+1);
        return std::max(lf , rg); 
    }
};
segt a;
/**/
/*functions*/
void addgte(ll y , ll ind){
    ll pl = std::min(10ll , n);
    for(ll i = pl;y <= i;i--){
        gt[i+1] = gt[i];
    }
    gt[y].sec = ind;
    for(ll i = y;0<=i;i--){
        gt[i].fi++;
        a.upd(0 , n-1 , gt[i].sec , 1 ,  gt[i].fi);
    }
    /*for(ll i = 0;pl>i;i++){
        std::cout << gt[i].fi << " " << gt[i].sec << "\n";
    }*/
}
void delgte(ll y){
    ll pl = std::min(10ll , n);
    for(ll i = y;pl>i;i++){
        gt[i] = gt[i-1];
    }
    gt[pl-1] = {0 , 0};
    /*for(ll i = 0;pl>i;i++){
        std::cout << gt[i].fi << " " << gt[i].sec << "\n";
    }
    std::cout << std::endl;*/
}
/**/
void solve(){
    std::cin >> n >> k;
    a.valt.resize(4*n+5);
    k--;
    ar.resize(n);
    for(ll i = 0 ; n>i;i++){
        std::cin >> ar[i].fi;
        ar[i].sec = i;
        a.upd(0 , n-1 , i , 1 , ar[i].fi);
    }
    std::sort(all(ar) , std::greater<llll>());
    ll pl = std::min(10ll , n);
    for(ll i = 0;pl>i;i++){
        gt[i] = ar[i];
    }
    ll q;std::cin >> q;
    while(q--){
        std::string h;ll x , y;std::cin >> h >> x;x--;
        if(h == "E"){
            std::cin >> y;y--;
            for(ll i = 0;pl>i;i++){
                if(gt[i].sec == x){
                    delgte(i);
                }
            }
            addgte(y , x);
        }
        else{
            if(k == n-1){
                std::cout << k - x;
            }
            else if(k == 0){
                std::cout << x - k;
            }
            else if(x > k){
                ll l = 0 , r = k-1;
                ll o = a.que(k+1 , x , 0 , n-1 , 1);
                while(r > l){
                    ll md = (l + r)/2;
                    ll s = a.que(md , k-1 , 0 , n-1 , 1);
                    if(s > o){
                        l = md+1;
                    }
                    else{
                        r = md;
                    }
                }
                ll ans = k - l;
                if(a.que(l , k-1 , 0 , n-1 , 1) > o){
                    ans = 0;
                }
                ans += x - k;
                std::cout << ans;
            }
            else if(k > x){
                ll l = k+1 , r = n-1;
                ll o = a.que(x , k-1 , 0 , n-1 , 1);
                //std::cout << o << "\n";
                while(r > l){
                    ll md = (l + r+1)/2;
                    ll s = a.que(k+1 , md , 0 , n-1 , 1);
                    if(s > o){
                        r = md-1;
                    }
                    else{
                        l = md;
                    }
                }
                ll ans = l - k;
                if(a.que(k+1 , l , 0 , n-1 , 1) > o){
                    ans = 0;
                }
                ans += k - x;
                std::cout << ans;
            }
            else{
                std::cout << "0";
            }
            if(q){
                std::cout << std::endl;
            }
        }
    
    }
    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")/**/
      |                                                                               
cake.cpp: In function 'int main()':
cake.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         freopen("in.txt" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         freopen("out.txt" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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