oj.uz

Submission #391863

# Submission time Handle Problem Language Result Execution time Memory
391863 2021-04-20T04:06:57 Z i_am_noob Cake (CEOI14_cake) C++17
20 / 100
 394 ms 3928 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
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 292 ms 332 KB Output isn't correct
2 Correct 311 ms 380 KB Output is correct
3 Incorrect 298 ms 332 KB Output isn't correct
4 Correct 335 ms 332 KB Output is correct
5 Incorrect 290 ms 496 KB Output isn't correct
6 Correct 302 ms 496 KB Output is correct
7 Incorrect 305 ms 508 KB Output isn't correct
8 Correct 394 ms 540 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1732 KB Output is correct
2 Correct 31 ms 1460 KB Output is correct
3 Correct 30 ms 1408 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 48 ms 2804 KB Output is correct
6 Correct 48 ms 2816 KB Output is correct
7 Correct 45 ms 2648 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 460 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 32 ms 864 KB Output is correct
5 Incorrect 55 ms 604 KB Output isn't correct
6 Incorrect 61 ms 1220 KB Output isn't correct
7 Incorrect 78 ms 864 KB Output isn't correct
8 Correct 132 ms 1108 KB Output is correct
9 Incorrect 216 ms 3896 KB Output isn't correct
10 Incorrect 184 ms 1328 KB Output isn't correct
11 Incorrect 188 ms 1728 KB Output isn't correct
12 Correct 215 ms 3368 KB Output is correct
13 Correct 233 ms 3928 KB Output is correct