oj.uz

답안 #391844

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391844 2021-04-20T03:36:12 Z i_am_noob 케이크 (CEOI14_cake) C++17
35 / 100
 186 ms 3832 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){
                vec.erase(vec.begin()+i);
                break;
            }
            vec.insert(vec.begin()+val,pos);
            for(auto i: vecl) bug(i.first,i.second);
            for(auto i: vecr) bug(i.first,i.second);
        }
        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:89:31: note: in expansion of macro 'bug'
   89 |             for(auto i: vecl) bug(i.first,i.second);
      |                               ^~~
cake.cpp:89:22: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   89 |             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:90:31: note: in expansion of macro 'bug'
   90 |             for(auto i: vecr) bug(i.first,i.second);
      |                               ^~~
cake.cpp:90:22: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   90 |             for(auto i: vecr) bug(i.first,i.second);
      |                      ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 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 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 384 KB Output is correct
2 Correct 116 ms 332 KB Output is correct
3 Correct 143 ms 380 KB Output is correct
4 Correct 114 ms 332 KB Output is correct
5 Correct 159 ms 460 KB Output is correct
6 Correct 139 ms 496 KB Output is correct
7 Correct 144 ms 516 KB Output is correct
8 Correct 118 ms 464 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 1644 KB Output is correct
2 Correct 31 ms 1536 KB Output is correct
3 Correct 31 ms 1424 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 51 ms 2916 KB Output is correct
6 Correct 49 ms 2888 KB Output is correct
7 Correct 58 ms 2628 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 460 KB Output isn't correct
2 Incorrect 15 ms 472 KB Output isn't correct
3 Incorrect 26 ms 844 KB Output isn't correct
4 Correct 26 ms 824 KB Output is correct
5 Incorrect 42 ms 580 KB Output isn't correct
6 Correct 45 ms 1236 KB Output is correct
7 Correct 56 ms 800 KB Output is correct
8 Correct 66 ms 1108 KB Output is correct
9 Correct 186 ms 3824 KB Output is correct
10 Incorrect 152 ms 1320 KB Output isn't correct
11 Correct 136 ms 1740 KB Output is correct
12 Correct 170 ms 3492 KB Output is correct
13 Correct 169 ms 3832 KB Output is correct