Submission #391860

# Submission time Handle Problem Language Result Execution time Memory
391860 2021-04-20T04:03:45 Z balbit Cake (CEOI14_cake) C++14
0 / 100
2000 ms 7632 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] <= 1000000) {
            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) > 1000000) 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;
            REP(j, SZ(v)) {
                if (v[j].s == i) {
                    v.erase(v.begin()+j);
                    break;
                }
            }
            MO(i, {e,q});
            v.pb({e,i});
            for (int j = SZ(v)-1; 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) > 1000000) {
                MO(v.back().s, {v.back().f,q});
                v.pop_back();
            }
//            a[i] = x;
//            MO(i,x);
        }
    }

}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 2 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 716 KB Time limit exceeded
2 Execution timed out 2089 ms 716 KB Time limit exceeded
3 Execution timed out 2089 ms 716 KB Time limit exceeded
4 Execution timed out 2076 ms 720 KB Time limit exceeded
5 Execution timed out 2093 ms 1104 KB Time limit exceeded
6 Execution timed out 2091 ms 1104 KB Time limit exceeded
7 Execution timed out 2063 ms 1104 KB Time limit exceeded
8 Execution timed out 2097 ms 1104 KB Time limit exceeded
# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 3516 KB Time limit exceeded
2 Execution timed out 2066 ms 3708 KB Time limit exceeded
3 Execution timed out 2080 ms 3644 KB Time limit exceeded
4 Incorrect 1 ms 332 KB Output isn't correct
5 Execution timed out 2081 ms 7596 KB Time limit exceeded
6 Execution timed out 2099 ms 7508 KB Time limit exceeded
7 Execution timed out 2079 ms 7632 KB Time limit exceeded
# Verdict Execution time Memory Grader output
1 Execution timed out 2016 ms 484 KB Time limit exceeded
2 Execution timed out 2067 ms 588 KB Time limit exceeded
3 Execution timed out 2088 ms 1856 KB Time limit exceeded
4 Execution timed out 2085 ms 1868 KB Time limit exceeded
5 Execution timed out 2084 ms 432 KB Time limit exceeded
6 Execution timed out 2088 ms 2756 KB Time limit exceeded
7 Execution timed out 2086 ms 772 KB Time limit exceeded
8 Execution timed out 2098 ms 3260 KB Time limit exceeded
9 Execution timed out 2099 ms 7404 KB Time limit exceeded
10 Execution timed out 2099 ms 444 KB Time limit exceeded
11 Execution timed out 2056 ms 1156 KB Time limit exceeded
12 Execution timed out 2092 ms 6072 KB Time limit exceeded
13 Execution timed out 2097 ms 7424 KB Time limit exceeded