oj.uz

Submission #391862

# Submission time Handle Problem Language Result Execution time Memory
391862 2021-04-20T04:06:08 Z i_am_noob Cake (CEOI14_cake) C++17
25 / 100
 346 ms 3952 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;
            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 if(pos>=x){
                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: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 376 KB Output is correct
2 Correct 291 ms 376 KB Output is correct
3 Correct 312 ms 388 KB Output is correct
4 Correct 331 ms 380 KB Output is correct
5 Correct 308 ms 496 KB Output is correct
6 Correct 306 ms 500 KB Output is correct
7 Correct 313 ms 500 KB Output is correct
8 Correct 346 ms 628 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1604 KB Output is correct
2 Correct 32 ms 1512 KB Output is correct
3 Correct 31 ms 1408 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Correct 49 ms 2848 KB Output is correct
6 Correct 50 ms 2964 KB Output is correct
7 Correct 46 ms 2616 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 380 KB Output isn't correct
2 Incorrect 20 ms 460 KB Output isn't correct
3 Incorrect 34 ms 844 KB Output isn't correct
4 Correct 33 ms 844 KB Output is correct
5 Incorrect 57 ms 552 KB Output isn't correct
6 Incorrect 63 ms 1172 KB Output isn't correct
7 Incorrect 79 ms 968 KB Output isn't correct
8 Correct 131 ms 1096 KB Output is correct
9 Incorrect 218 ms 3840 KB Output isn't correct
10 Incorrect 188 ms 1416 KB Output isn't correct
11 Incorrect 178 ms 1804 KB Output isn't correct
12 Correct 214 ms 3380 KB Output is correct
13 Correct 235 ms 3952 KB Output is correct