oj.uz

Submission #391815

# Submission time Handle Problem Language Result Execution time Memory
391815 2021-04-20T03:18:27 Z balbit Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 8644 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 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 = 1e9+8;
pii s[maxn*4];
pii 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, {0,-1});
    a[0] = {0,-1};
    REP1(i,n) {
        int y; cin>>y;
        a[i] = {n-y+1,inf};
        MO(i,a[i]);
    }
    a[n+1] = {0,-1};
    MO(n+1,{0,-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 = i, R = i<st?st-1:st+1;
                if (L>R) swap(L,R);
                pii hi = QU(L,R);
//                bug(hi.f, hi.s);
                int x;
                if (i<st) {
                    for (int i = st+1; ; ++i) {
                        if (a[i] < hi) {
                            x=i; break;
                        }
                    }
//                    x = bigger(st+1,hi);
                }else{
                    for (int i = st-1;; --i) {
                        if (a[i] < hi) {
                            x = i; break;
                        }
                    }
//                    x = biggerl(st-1,hi);
                }
//                bug(x);
                cout<<abs(x-i)-1<<'\n';

            }
        }else{
            int e; cin>>e;
            a[i] = {e,q};
            MO(i,{e,q});
        }
    }

}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 4920 KB Output isn't correct
2 Correct 193 ms 5064 KB Output is correct
3 Incorrect 204 ms 4952 KB Output isn't correct
4 Correct 198 ms 5068 KB Output is correct
5 Incorrect 236 ms 5572 KB Output isn't correct
6 Incorrect 216 ms 6028 KB Output isn't correct
7 Incorrect 228 ms 5704 KB Output isn't correct
8 Correct 201 ms 5964 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 4472 KB Time limit exceeded
2 Execution timed out 2083 ms 4488 KB Time limit exceeded
3 Execution timed out 2075 ms 4012 KB Time limit exceeded
4 Incorrect 1 ms 332 KB Output isn't correct
5 Execution timed out 2062 ms 8544 KB Time limit exceeded
6 Execution timed out 2050 ms 8436 KB Time limit exceeded
7 Execution timed out 2075 ms 8316 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 868 KB Output isn't correct
2 Incorrect 127 ms 1004 KB Output isn't correct
3 Incorrect 1481 ms 2700 KB Output isn't correct
4 Incorrect 1016 ms 2732 KB Output isn't correct
5 Incorrect 181 ms 1864 KB Output isn't correct
6 Execution timed out 2078 ms 3792 KB Time limit exceeded
7 Incorrect 708 ms 2680 KB Output isn't correct
8 Incorrect 328 ms 5212 KB Output isn't correct
9 Execution timed out 2058 ms 8620 KB Time limit exceeded
10 Incorrect 594 ms 5196 KB Output isn't correct
11 Execution timed out 2072 ms 4780 KB Time limit exceeded
12 Execution timed out 2091 ms 7248 KB Time limit exceeded
13 Execution timed out 2071 ms 8644 KB Time limit exceeded