oj.uz

Submission #392382

# Submission time Handle Problem Language Result Execution time Memory
392382 2021-04-21T01:00:30 Z i_am_noob Cake (CEOI14_cake) C++17
100 / 100
 186 ms 9312 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define ll int_fast64_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 204 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 5 ms 476 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 3724 KB Output is correct
2 Correct 134 ms 3784 KB Output is correct
3 Correct 153 ms 3768 KB Output is correct
4 Correct 128 ms 3828 KB Output is correct
5 Correct 168 ms 3784 KB Output is correct
6 Correct 146 ms 3792 KB Output is correct
7 Correct 149 ms 3780 KB Output is correct
8 Correct 126 ms 3840 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2624 KB Output is correct
2 Correct 39 ms 2400 KB Output is correct
3 Correct 31 ms 2384 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 50 ms 4292 KB Output is correct
6 Correct 50 ms 4268 KB Output is correct
7 Correct 48 ms 4200 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 828 KB Output is correct
2 Correct 15 ms 852 KB Output is correct
3 Correct 27 ms 1588 KB Output is correct
4 Correct 27 ms 1544 KB Output is correct
5 Correct 44 ms 1632 KB Output is correct
6 Correct 48 ms 2628 KB Output is correct
7 Correct 53 ms 2408 KB Output is correct
8 Correct 71 ms 3120 KB Output is correct
9 Correct 186 ms 9312 KB Output is correct
10 Correct 142 ms 4804 KB Output is correct
11 Correct 142 ms 5984 KB Output is correct
12 Correct 179 ms 8536 KB Output is correct
13 Correct 176 ms 9244 KB Output is correct