oj.uz

Submission #391829

# Submission time Handle Problem Language Result Execution time Memory
391829 2021-04-20T03:24:35 Z balbit Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 6688 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 = 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);
                pii hi = {inf, 1000000};
//                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;
            a[i] = {e,q};
            MO(i,{e,q});
        }
    }

}

Subtask #1
0 / 15.0

# 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 -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 588 KB Output isn't correct
2 Correct 188 ms 588 KB Output is correct
3 Incorrect 244 ms 588 KB Output isn't correct
4 Correct 187 ms 620 KB Output is correct
5 Incorrect 237 ms 976 KB Output isn't correct
6 Incorrect 217 ms 908 KB Output isn't correct
7 Incorrect 241 ms 884 KB Output isn't correct
8 Correct 206 ms 972 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 3072 KB Time limit exceeded
2 Execution timed out 2067 ms 3144 KB Time limit exceeded
3 Execution timed out 2068 ms 2996 KB Time limit exceeded
4 Incorrect 1 ms 332 KB Output isn't correct
5 Execution timed out 2076 ms 6636 KB Time limit exceeded
6 Execution timed out 2080 ms 6544 KB Time limit exceeded
7 Execution timed out 2071 ms 6688 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 552 KB Output isn't correct
2 Incorrect 190 ms 580 KB Output isn't correct
3 Execution timed out 2070 ms 1788 KB Time limit exceeded
4 Incorrect 1460 ms 1860 KB Output isn't correct
5 Incorrect 206 ms 848 KB Output isn't correct
6 Execution timed out 2070 ms 2216 KB Time limit exceeded
7 Incorrect 1157 ms 1192 KB Output isn't correct
8 Incorrect 324 ms 2792 KB Output isn't correct
9 Execution timed out 2083 ms 6452 KB Time limit exceeded
10 Incorrect 669 ms 1472 KB Output isn't correct
11 Execution timed out 2036 ms 1548 KB Time limit exceeded
12 Execution timed out 2072 ms 5376 KB Time limit exceeded
13 Execution timed out 2084 ms 6428 KB Time limit exceeded