oj.uz

Submission #391856

# Submission time Handle Problem Language Result Execution time Memory
391856 2021-04-20T03:54:31 Z i_am_noob Cake (CEOI14_cake) C++17
35 / 100
 319 ms 3892 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--;
            if(pos==x) continue;
            rep(val) a[vec[i]]++;
            a[pos]=a[vec[val]]+1;
            if(pos<x){
                vector<pii> tmp;
                for(int i=sz(vecl)-1; i>=0&&vecl[i].first>=a[pos]&&vecl[i].second!=pos; --i) vecl[i].first++;
                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();


                for(int i=sz(vecr)-1; i>=0&&vecr[i].first>=a[pos]; --i) vecr[i].first++;
            }
            else{
                vector<pii> tmp;
                for(int i=sz(vecr)-1; i>=0&&vecr[i].first>=a[pos]&&vecr[i].second!=pos; --i) vecr[i].first++;
                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();

                for(int i=sz(vecl)-1; i>=0&&vecl[i].first>=a[pos]; --i) vecl[i].first++;
            }
            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:96:31: note: in expansion of macro 'bug'
   96 |             for(auto i: vecl) bug(i.first,i.second);
      |                               ^~~
cake.cpp:96:22: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   96 |             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:97:31: note: in expansion of macro 'bug'
   97 |             for(auto i: vecr) bug(i.first,i.second);
      |                               ^~~
cake.cpp:97:22: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   97 |             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:99:30: note: in expansion of macro 'bug'
   99 |             for(auto i: vec) bug(i);
      |                              ^~~
cake.cpp:99:22: warning: unused variable 'i' [-Wunused-variable]
   99 |             for(auto i: vec) bug(i);
      |                      ^

Subtask #1
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 Incorrect 2 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 380 KB Output is correct
2 Correct 276 ms 332 KB Output is correct
3 Correct 297 ms 380 KB Output is correct
4 Correct 316 ms 376 KB Output is correct
5 Correct 293 ms 496 KB Output is correct
6 Correct 289 ms 512 KB Output is correct
7 Correct 298 ms 500 KB Output is correct
8 Correct 319 ms 584 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1632 KB Output is correct
2 Correct 31 ms 1500 KB Output is correct
3 Correct 30 ms 1492 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 48 ms 2884 KB Output is correct
6 Correct 52 ms 2868 KB Output is correct
7 Correct 45 ms 2700 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 460 KB Output isn't correct
2 Incorrect 19 ms 460 KB Output isn't correct
3 Incorrect 33 ms 804 KB Output isn't correct
4 Correct 31 ms 836 KB Output is correct
5 Incorrect 53 ms 580 KB Output isn't correct
6 Correct 60 ms 1192 KB Output is correct
7 Correct 70 ms 836 KB Output is correct
8 Correct 127 ms 1084 KB Output is correct
9 Correct 204 ms 3792 KB Output is correct
10 Incorrect 179 ms 1484 KB Output isn't correct
11 Correct 170 ms 1712 KB Output is correct
12 Correct 200 ms 3396 KB Output is correct
13 Correct 224 ms 3892 KB Output is correct