oj.uz

답안 #391865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391865 2021-04-20T04:10:37 Z balbit 케이크 (CEOI14_cake) C++14
100 / 100
 980 ms 7012 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define MN(a,b) a = min(a,b)
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#ifdef BALBIT
#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(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 250005;
const int inf = 2e9+8;
const int hinf= inf/2;
pii s[maxn*4];
int a[maxn];

pii QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
    if ( l> R || r < L) return {inf, -1};
    if (l>=L && r <= R) return s[o];
    int mid = (l+r)/2;
    return min(QU(L,R,o*2,l,mid), QU(L,R,o*2+1,mid+1,r));
}

void MO(int p, pii v, int o=1, int l=0, int r=maxn-1) {
    if (l > p || r < p) return;
    if( l == r) {
        s[o] = v; return;
    }
    int mid = (l+r)/2;
    MO(p,v,o*2,l,mid);
    MO(p,v,o*2+1,mid+1,r);
    s[o] = min(s[o*2], s[o*2+1]);
}

int bigger(int p, pii v, int o=1, int l=0, int r = maxn-1) {
    if (r < p || s[o] > v) return -1; // first thing geq v position >= p
    if (l == r) {
        return l;
    }
    int mid = (l+r)/2;
    if (l >= p) {
        if (s[o*2] <= v) return bigger(p,v,o*2,l,mid);
        else return bigger(p,v,o*2+1,mid+1,r);
    }else{
        int yy = bigger(p,v,o*2,l,mid);
        if (yy!=-1) return yy;
        return bigger(p,v,o*2+1,mid+1,r);
    }
}

int biggerl(int p, pii v, int o=1, int l=0, int r = maxn-1) {
//        bug(p,o,l,r);
    if (l > p || s[o] > v) return -1; // first thing geq v position <= p
    if (l == r) {
        return l;
    }
    int mid = (l+r)/2;
    if (r <= p) {
        if (s[o*2+1] <= v) return biggerl(p,v,o*2+1,mid+1,r);
        else return biggerl(p,v,o*2,l,mid);
    }else{
        int yy = biggerl(p,v,o*2+1,mid+1,r);
        if (yy!=-1) return yy;
        return biggerl(p,v,o*2,l,mid);
    }
}



signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);
    int n,st; cin>>n>>st;
    MO(0, {-inf,-1});
//    a[0] = {-inf, -1};
    vector<pair<int, int> > v;
    REP1(i,n) {
        int y; cin>>y;
        a[i] = n-y+1;
        if (a[i] <= 10) {
            v.pb({a[i], i});
        }else{
//            a[i] += hinf;
        }
//        bug(a[i].f, a[i].s);
        MO(i,{a[i], inf});
    }
    sort(ALL(v));
    while (SZ(v) > 10) v.pop_back();
//    a[n+1] = {-inf,-1};
    MO(n+1,{-inf,-1});
    int q; cin>>q;
    while (q--) {
        char c; cin>>c;
        int i; cin>>i;
        if (c == 'F') {
            if (st == i) cout<<0<<endl;
            else{
//                {
//                    int L = st, R = st;
//                    while (i < L || i > R) {
//                        if (a[L-1] > a[R+1]) --L;
//                        else ++R;
//                    }
//                    cout<<R-L<<endl;
//                }
//                continue;
                int L = i, R = i<st?st-1:st+1;
                if (L>R) swap(L,R);
                pii hi = QU(L,R);
//                int hi = inf;
//                bug(hi.f, hi.s);
                int x;
                if (i<st) {
//                    for (int j = i; j<st; ++j) {
//                        MN(hi, a[j]);
//                    }
//                    for (int j = st+1; ; ++j) {
//                        if (a[j] < hi) {
//                            x=j; break;
//                        }
//                    }
                    x = bigger(st+1,hi);
                }else{
//                    for (int j = i; j>st; --j) {
//                        MN(hi, a[j]);
//                    }
//                    for (int j = st-1;; --j) {
//                        if (a[j] < hi) {
//                            x = j; break;
//                        }
//                    }
                    x = biggerl(st-1,hi);
                }
//                bug(x);
                cout<<abs(x-i)-1<<'\n';

            }
        }else{
            int e; cin>>e;
            int at = SZ(v);
            bool in = 0;
            REP(j, SZ(v)) {
                if (v[j].s == i) {
                    at = j; in = 1;
                    break;
                }
            }
//            for (pii p : v) cout<<p.s<<' ';
//            cout<<endl;

            MO(i, {e,q});
            if (!in) {
                v.pb({e,i});
                at = SZ(v)-1;
            }else{
                v[at].f = e;
            }
            for (int j = at; j>0; --j) {
                if (v[j-1].f >= e) {
                    swap(v[j-1], v[j]);
                    ++v[j].f;
                    MO(v[j].s, {v[j].f,q});
                }else break;
            }
            while (SZ(v) > 10) {
                MO(v.back().s, {v.back().f,q});
                v.pop_back();
            }
//            a[i] = x;
//            MO(i,x);
        }
    }

}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 10 ms 400 KB Output is correct
5 Correct 20 ms 604 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 589 ms 540 KB Output is correct
2 Correct 319 ms 460 KB Output is correct
3 Correct 558 ms 560 KB Output is correct
4 Correct 307 ms 460 KB Output is correct
5 Correct 622 ms 852 KB Output is correct
6 Correct 480 ms 844 KB Output is correct
7 Correct 561 ms 864 KB Output is correct
8 Correct 318 ms 856 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 2884 KB Output is correct
2 Correct 103 ms 2852 KB Output is correct
3 Correct 93 ms 2796 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 183 ms 6024 KB Output is correct
6 Correct 168 ms 5948 KB Output is correct
7 Correct 143 ms 5828 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 476 KB Output is correct
2 Correct 98 ms 496 KB Output is correct
3 Correct 182 ms 1528 KB Output is correct
4 Correct 141 ms 1680 KB Output is correct
5 Correct 212 ms 632 KB Output is correct
6 Correct 327 ms 2096 KB Output is correct
7 Correct 389 ms 972 KB Output is correct
8 Correct 346 ms 2324 KB Output is correct
9 Correct 980 ms 6996 KB Output is correct
10 Correct 702 ms 1460 KB Output is correct
11 Correct 778 ms 2036 KB Output is correct
12 Correct 955 ms 6012 KB Output is correct
13 Correct 729 ms 7012 KB Output is correct