oj.uz

Submission #391984

# Submission time Handle Problem Language Result Execution time Memory
391984 2021-04-20T09:22:03 Z i_am_noob Cake (CEOI14_cake) C++17
100 / 100
 198 ms 3884 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll int_fast32_t
#define int ll
#define rep(n) rep1(i,n)
#define rep1(i,n) rep2(i,0,n)
#define rep2(i,a,b) for(int i=a; i<(b); ++i)
#define rep3(i,a,b) for(int i=a; i>=(b); --i)
#define pb push_back
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))

#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << " " << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T x){cerr << x << endl;}
template<typename T, typename ...S> void _do(T x, S ...y){cerr << x << ", ";_do(y...);}
#else
#define bug(...) 49
#endif

const int maxn=300005;

int n,x,a[maxn],q,cur;
vector<int> vec;
vector<pii> vecl,vecr;

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> x;
    x--;
    rep(n) cin >> a[i];
    rep(n) a[i]--;
    vec.resize(min(n,(int)10));
    rep(n) if(a[i]>=n-10) vec[n-a[i]-1]=i;
    rep(sz(vec)-1) assert(a[vec[i]]>a[vec[i+1]]);
    rep3(i,x-1,0){
        if(vecl.empty()||a[i]>vecl.back().first) vecl.pb({a[i],i});
    }
    rep2(i,x+1,n){
        if(vecr.empty()||a[i]>vecr.back().first) vecr.pb({a[i],i});
    }
    vecl.pb({inf,-1}),vecr.pb({inf,n});
    cur=n;
    cin >> q;
    while(q--){
        char op;
        cin >> op;
        if(op=='E'){
            int pos,val;
            cin >> pos >> val;
            pos--,val--;
            rep(val) a[vec[i]]++;
            a[pos]=a[vec[val]]+1;
            for(int i=sz(vecl)-1; i>=0&&vecl[i].first>=a[pos]&&vecl[i].second!=pos; --i) vecl[i].first++;
            for(int i=sz(vecr)-1; i>=0&&vecr[i].first>=a[pos]&&vecr[i].second!=pos; --i) vecr[i].first++;
            if(pos<x){
                vector<pii> tmp;
                
                while(sz(vecl)&&(vecl.back().second<=pos)){
                    if(vecl.back().first>a[pos]) tmp.pb(vecl.back());
                    vecl.pop_back();
                }
                if(vecl.empty()||(vecl.back().second>pos&&vecl.back().first<a[pos])) vecl.pb({a[pos],pos});
                while(sz(tmp)) vecl.pb(tmp.back()),tmp.pop_back();

            }
            else if(pos>x){
                vector<pii> tmp;
                
                while(sz(vecr)&&vecr.back().second>=pos){
                    if(vecr.back().first>a[pos]) tmp.pb(vecr.back());
                    vecr.pop_back();
                }
                if(vecr.empty()||(vecr.back().second<pos&&vecr.back().first<a[pos])) vecr.pb({a[pos],pos});
                while(sz(tmp)) vecr.pb(tmp.back()),tmp.pop_back();

            }
            cur++;
            rep(sz(vec)) if(vec[i]==pos||i==sz(vec)-1){
                vec.erase(vec.begin()+i);
                break;
            }
            vec.insert(vec.begin()+val,pos);
        }
        else{
            int pos;
            cin >> pos;
            pos--;
            if(pos==x){
                cout << "0\n";
                continue;
            }
            if(pos<x){
                pii tmp={a[pos],pos};
                pii p=*--upper_bound(all(vecl),tmp,[&](const pii& i,const pii& j){return i.second>j.second;});
                pii q=*upper_bound(all(vecr),p);
                cout << q.second-pos-1 << "\n";
            }
            else{
                pii tmp={a[pos],pos};
                pii p=*--upper_bound(all(vecr),tmp,[&](const pii& i,const pii& j){return i.second<j.second;});
                pii q=*upper_bound(all(vecl),p);
                cout << pos-q.second-1 << "\n";
            }
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 236 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 380 KB Output is correct
2 Correct 121 ms 388 KB Output is correct
3 Correct 147 ms 380 KB Output is correct
4 Correct 124 ms 332 KB Output is correct
5 Correct 169 ms 496 KB Output is correct
6 Correct 153 ms 504 KB Output is correct
7 Correct 143 ms 500 KB Output is correct
8 Correct 134 ms 460 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1608 KB Output is correct
2 Correct 38 ms 1548 KB Output is correct
3 Correct 30 ms 1476 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 48 ms 2896 KB Output is correct
6 Correct 50 ms 2884 KB Output is correct
7 Correct 46 ms 2584 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 460 KB Output is correct
2 Correct 20 ms 460 KB Output is correct
3 Correct 25 ms 888 KB Output is correct
4 Correct 38 ms 844 KB Output is correct
5 Correct 42 ms 556 KB Output is correct
6 Correct 48 ms 1260 KB Output is correct
7 Correct 57 ms 816 KB Output is correct
8 Correct 67 ms 1208 KB Output is correct
9 Correct 198 ms 3872 KB Output is correct
10 Correct 140 ms 1324 KB Output is correct
11 Correct 139 ms 1928 KB Output is correct
12 Correct 177 ms 3440 KB Output is correct
13 Correct 172 ms 3884 KB Output is correct