oj.uz

답안 #709221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709221 2023-03-13T08:41:38 Z ktkerem 케이크 (CEOI14_cake) C++17
0 / 100
 2000 ms 13080 KB 
/*#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();
    }
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2059 ms 12324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2070 ms 12060 KB Time limit exceeded
2 Execution timed out 2077 ms 12396 KB Time limit exceeded
3 Execution timed out 2079 ms 12508 KB Time limit exceeded
4 Execution timed out 2049 ms 12256 KB Time limit exceeded
5 Execution timed out 2069 ms 12548 KB Time limit exceeded
6 Execution timed out 2078 ms 12976 KB Time limit exceeded
7 Execution timed out 2021 ms 12384 KB Time limit exceeded
8 Execution timed out 2054 ms 12992 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2071 ms 13048 KB Time limit exceeded
2 Execution timed out 2065 ms 12528 KB Time limit exceeded
3 Execution timed out 2066 ms 12472 KB Time limit exceeded
4 Execution timed out 2081 ms 12724 KB Time limit exceeded
5 Execution timed out 2067 ms 12940 KB Time limit exceeded
6 Execution timed out 2044 ms 12892 KB Time limit exceeded
7 Execution timed out 2066 ms 12140 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2066 ms 13080 KB Time limit exceeded
2 Execution timed out 2060 ms 12996 KB Time limit exceeded
3 Execution timed out 2070 ms 12148 KB Time limit exceeded
4 Execution timed out 2064 ms 12628 KB Time limit exceeded
5 Execution timed out 2076 ms 12796 KB Time limit exceeded
6 Execution timed out 2083 ms 12404 KB Time limit exceeded
7 Execution timed out 2078 ms 12776 KB Time limit exceeded
8 Execution timed out 2076 ms 12408 KB Time limit exceeded
9 Execution timed out 2073 ms 12816 KB Time limit exceeded
10 Execution timed out 2070 ms 12812 KB Time limit exceeded
11 Execution timed out 2068 ms 12612 KB Time limit exceeded
12 Execution timed out 2057 ms 13012 KB Time limit exceeded
13 Execution timed out 2037 ms 12152 KB Time limit exceeded