oj.uz

답안 #391835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391835 2021-04-20T03:28:00 Z balbit 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 6656 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 = 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);
                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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 224 ms 588 KB Output isn't correct
2 Correct 240 ms 604 KB Output is correct
3 Incorrect 205 ms 588 KB Output isn't correct
4 Correct 193 ms 608 KB Output is correct
5 Incorrect 238 ms 972 KB Output isn't correct
6 Incorrect 213 ms 976 KB Output isn't correct
7 Incorrect 233 ms 1092 KB Output isn't correct
8 Correct 207 ms 984 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2050 ms 2880 KB Time limit exceeded
2 Execution timed out 2069 ms 3096 KB Time limit exceeded
3 Execution timed out 2082 ms 2924 KB Time limit exceeded
4 Incorrect 1 ms 332 KB Output isn't correct
5 Execution timed out 2072 ms 6416 KB Time limit exceeded
6 Execution timed out 2072 ms 6428 KB Time limit exceeded
7 Execution timed out 2073 ms 6656 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 120 ms 592 KB Output isn't correct
2 Incorrect 312 ms 512 KB Output isn't correct
3 Execution timed out 2082 ms 1752 KB Time limit exceeded
4 Execution timed out 2011 ms 1856 KB Time limit exceeded
5 Incorrect 263 ms 628 KB Output isn't correct
6 Execution timed out 2099 ms 2032 KB Time limit exceeded
7 Incorrect 1435 ms 1180 KB Output isn't correct
8 Incorrect 405 ms 2784 KB Output isn't correct
9 Execution timed out 2082 ms 6540 KB Time limit exceeded
10 Incorrect 881 ms 1476 KB Output isn't correct
11 Execution timed out 2085 ms 1508 KB Time limit exceeded
12 Execution timed out 2085 ms 5272 KB Time limit exceeded
13 Execution timed out 2074 ms 6540 KB Time limit exceeded