Submission #391858

# Submission time Handle Problem Language Result Execution time Memory
391858 2021-04-20T03:59:32 Z balbit Cake (CEOI14_cake) C++14
0 / 100
1282 ms 7108 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;
            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) > 10) {
                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 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1272 ms 544 KB Output isn't correct
2 Correct 1135 ms 692 KB Output is correct
3 Incorrect 1195 ms 564 KB Output isn't correct
4 Correct 1248 ms 564 KB Output is correct
5 Incorrect 1278 ms 860 KB Output isn't correct
6 Correct 1165 ms 844 KB Output is correct
7 Incorrect 1282 ms 880 KB Output isn't correct
8 Correct 1242 ms 864 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 114 ms 2884 KB Output is correct
2 Correct 105 ms 2756 KB Output is correct
3 Correct 94 ms 2864 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Correct 178 ms 6032 KB Output is correct
6 Incorrect 168 ms 5948 KB Output isn't correct
7 Correct 151 ms 5744 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 540 KB Output isn't correct
2 Incorrect 97 ms 484 KB Output isn't correct
3 Incorrect 177 ms 1476 KB Output isn't correct
4 Incorrect 154 ms 1476 KB Output isn't correct
5 Incorrect 213 ms 720 KB Output isn't correct
6 Correct 337 ms 2060 KB Output is correct
7 Incorrect 394 ms 948 KB Output isn't correct
8 Incorrect 582 ms 2520 KB Output isn't correct
9 Incorrect 989 ms 7032 KB Output isn't correct
10 Incorrect 733 ms 1456 KB Output isn't correct
11 Incorrect 770 ms 2116 KB Output isn't correct
12 Incorrect 951 ms 6096 KB Output isn't correct
13 Incorrect 884 ms 7108 KB Output isn't correct