답안 #391850

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391850 2021-04-20T03:44:46 Z i_am_noob 케이크 (CEOI14_cake) C++17
10 / 100
351 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;
    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 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 189 ms 636 KB Execution killed with signal 6
2 Correct 307 ms 452 KB Output is correct
3 Correct 306 ms 332 KB Output is correct
4 Correct 351 ms 380 KB Output is correct
5 Runtime error 7 ms 844 KB Execution killed with signal 6
6 Correct 301 ms 504 KB Output is correct
7 Correct 306 ms 508 KB Output is correct
8 Correct 338 ms 580 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 1656 KB Output is correct
2 Correct 33 ms 1568 KB Output is correct
3 Correct 31 ms 1428 KB Output is correct
4 Runtime error 1 ms 460 KB Execution killed with signal 6
5 Correct 53 ms 2924 KB Output is correct
6 Correct 48 ms 2884 KB Output is correct
7 Correct 45 ms 2628 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 444 KB Output isn't correct
2 Incorrect 21 ms 472 KB Output isn't correct
3 Incorrect 34 ms 844 KB Output isn't correct
4 Correct 34 ms 896 KB Output is correct
5 Incorrect 56 ms 584 KB Output isn't correct
6 Correct 64 ms 1156 KB Output is correct
7 Correct 72 ms 848 KB Output is correct
8 Correct 131 ms 1100 KB Output is correct
9 Correct 213 ms 3900 KB Output is correct
10 Incorrect 178 ms 1348 KB Output isn't correct
11 Correct 173 ms 1768 KB Output is correct
12 Correct 214 ms 3776 KB Output is correct
13 Correct 228 ms 3928 KB Output is correct