답안 #391852

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391852 2021-04-20T03:47:01 Z i_am_noob 케이크 (CEOI14_cake) C++17
35 / 100
330 ms 3916 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;
    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));
            //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:95:31: note: in expansion of macro 'bug'
   95 |             for(auto i: vecl) bug(i.first,i.second);
      |                               ^~~
cake.cpp:95:22: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   95 |             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:96:31: note: in expansion of macro 'bug'
   96 |             for(auto i: vecr) bug(i.first,i.second);
      |                               ^~~
cake.cpp:96:22: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   96 |             for(auto i: vecr) bug(i.first,i.second);
      |                      ^
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 Grader output
1 Correct 281 ms 332 KB Output is correct
2 Correct 295 ms 384 KB Output is correct
3 Correct 316 ms 376 KB Output is correct
4 Correct 327 ms 376 KB Output is correct
5 Correct 303 ms 500 KB Output is correct
6 Correct 297 ms 460 KB Output is correct
7 Correct 310 ms 500 KB Output is correct
8 Correct 330 ms 496 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 1612 KB Output is correct
2 Correct 32 ms 1512 KB Output is correct
3 Correct 30 ms 1472 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 48 ms 2868 KB Output is correct
6 Correct 48 ms 2864 KB Output is correct
7 Correct 54 ms 2692 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 432 KB Output isn't correct
2 Incorrect 19 ms 372 KB Output isn't correct
3 Incorrect 33 ms 824 KB Output isn't correct
4 Correct 32 ms 928 KB Output is correct
5 Incorrect 54 ms 584 KB Output isn't correct
6 Correct 61 ms 1160 KB Output is correct
7 Correct 74 ms 784 KB Output is correct
8 Correct 127 ms 1228 KB Output is correct
9 Correct 226 ms 3916 KB Output is correct
10 Incorrect 178 ms 1348 KB Output isn't correct
11 Correct 173 ms 1788 KB Output is correct
12 Correct 206 ms 3416 KB Output is correct
13 Correct 223 ms 3872 KB Output is correct