oj.uz

Submission #391864

# Submission time Handle Problem Language Result Execution time Memory
391864 2021-04-20T04:08:55 Z i_am_noob Cake (CEOI14_cake) C++17
100 / 100
 340 ms 3908 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#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,10ll));
    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){
                vector<int> tmp;
                while(sz(vec)>i) tmp.pb(vec.back()),vec.pop_back();
                tmp.pop_back();
                while(sz(tmp)) vec.pb(tmp.back()),tmp.pop_back();
                break;
            }
            vector<int> tmp;
            while(sz(vec)>val) tmp.pb(vec.back()),vec.pop_back();
            vec.pb(pos);
            while(sz(tmp)) vec.pb(tmp.back()),tmp.pop_back();
            for(auto i: vecl) bug(i.first,i.second);
            for(auto i: vecr) bug(i.first,i.second);
            assert(sz(vec)==min(n,10ll));
            for(auto i: vec) bug(i);
            rep(sz(vec)-1) assert(a[vec[i]]>a[vec[i+1]]);
        }
        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";
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:22:18: warning: statement has no effect [-Wunused-value]
   22 | #define bug(...) 49
      |                  ^~
cake.cpp:94:31: note: in expansion of macro 'bug'
   94 |             for(auto i: vecl) bug(i.first,i.second);
      |                               ^~~
cake.cpp:94:22: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   94 |             for(auto i: vecl) bug(i.first,i.second);
      |                      ^
cake.cpp:22:18: warning: statement has no effect [-Wunused-value]
   22 | #define bug(...) 49
      |                  ^~
cake.cpp:95:31: note: in expansion of macro 'bug'
   95 |             for(auto i: vecr) bug(i.first,i.second);
      |                               ^~~
cake.cpp:95:22: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   95 |             for(auto i: vecr) bug(i.first,i.second);
      |                      ^
cake.cpp:22:18: warning: statement has no effect [-Wunused-value]
   22 | #define bug(...) 49
      |                  ^~
cake.cpp:97:30: note: in expansion of macro 'bug'
   97 |             for(auto i: vec) bug(i);
      |                              ^~~
cake.cpp:97:22: warning: unused variable 'i' [-Wunused-variable]
   97 |             for(auto i: vec) bug(i);
      |                      ^

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 392 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 392 KB Output is correct
2 Correct 279 ms 332 KB Output is correct
3 Correct 340 ms 396 KB Output is correct
4 Correct 323 ms 500 KB Output is correct
5 Correct 315 ms 496 KB Output is correct
6 Correct 297 ms 464 KB Output is correct
7 Correct 312 ms 496 KB Output is correct
8 Correct 326 ms 572 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1632 KB Output is correct
2 Correct 33 ms 1508 KB Output is correct
3 Correct 32 ms 1428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 49 ms 2908 KB Output is correct
6 Correct 49 ms 2884 KB Output is correct
7 Correct 46 ms 2688 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 416 KB Output is correct
2 Correct 20 ms 460 KB Output is correct
3 Correct 35 ms 844 KB Output is correct
4 Correct 33 ms 912 KB Output is correct
5 Correct 56 ms 640 KB Output is correct
6 Correct 62 ms 1220 KB Output is correct
7 Correct 74 ms 880 KB Output is correct
8 Correct 132 ms 1100 KB Output is correct
9 Correct 219 ms 3844 KB Output is correct
10 Correct 181 ms 1360 KB Output is correct
11 Correct 179 ms 1836 KB Output is correct
12 Correct 213 ms 3384 KB Output is correct
13 Correct 229 ms 3908 KB Output is correct