oj.uz

답안 #391827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391827 2021-04-20T03:22:00 Z wiwiho 케이크 (CEOI14_cake) C++14
0 / 100
 564 ms 81744 KB 
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define printv(a, b) {\
    for(auto pv : a) b << pv << " ";\
    b << "\n";\
}

using namespace std;

using pii = pair<int, int>;

ostream& operator<<(ostream& o, pii p){
    return o << '(' << p.F << ',' << p.S << ')';
}

void waassert(bool t){
    if(t) return;
    cout << "OAO\n";
    exit(0);
}

struct Node{
    int mn = 0, mx = 0, tag = -1, d = -1, sz;
    int l = -1, r = -1;
    int rmn(){
        if(tag == -1) return mn;
        return min(tag, tag + d * (sz - 1));
    }
    int rmx(){
        if(tag == -1) return mx;
        return max(tag, tag + d * (sz - 1));
    }
};

struct SegmentTree{
    vector<Node> st;
    int ts = 0;
    int lr, rr;
    void init(int n, int _lr, int _rr){
        st.resize(2 * n);
        lr = _lr;
        rr = _rr;
    }

    void push(int id){
        if(st[id].tag == -1) return;
        int lc = st[id].l, rc = st[id].r;
        st[lc].tag = st[id].tag;
        st[rc].tag = st[id].tag + st[id].d * st[lc].sz;
        st[lc].d = st[rc].d = st[id].d;
        st[id].mn = st[id].rmn();
        st[id].mx = st[id].rmx();
        st[id].tag = st[id].d = -1;
    }

    int build(int l = -1, int r = -1){
        if(l == -1) l = lr;
        if(r == -1) r = rr;
        int id = ts++;
        st[id].sz = r - l + 1;
        if(l == r) return id;
        int m = (l + r) / 2;
        st[id].l = build(l, m);
        st[id].r = build(m + 1, r);
        return id;
    }

    void modify(int l, int r, int f, int d = 0, int L = -1, int R = -1, int id = 0){
        if(L == -1) L = lr;
        if(R == -1) R = rr;
        //cerr << "modify " << l << " " << r << " " << f << " " << d << " " << L << " " << R << "\n";
        waassert(L <= l && r <= R && l <= r);
        if(l == L && r == R){
            st[id].tag = f;
            st[id].d = d;
            return;
        }
        push(id);
        int M = (L + R) / 2;
        if(r <= M) modify(l, r, f, d, L, M, st[id].l);
        else if(l > M) modify(l, r, f, d, M + 1, R, st[id].r);
        else{
            modify(l, M, f, d, L, M, st[id].l);
            modify(M + 1, r, f + d * (M + 1 - l), d, M + 1, R, st[id].r);
        }
        st[id].mn = min(st[st[id].l].rmn(), st[st[id].r].rmn());
        st[id].mx = max(st[st[id].l].rmx(), st[st[id].r].rmx());
    }

    int querymn(int l, int r, int L = -1, int R = -1, int id = 0){
        if(L == -1) L = lr;
        if(R == -1) R = rr;
        //waassert(L <= l && r <= R && l <= r);
        if(l == L && r == R) return st[id].rmn();
        push(id);
        int M = (L + R) / 2;
        if(r <= M) return querymn(l, r, L, M, st[id].l);
        else if(l > M) return querymn(l, r, M + 1, R, st[id].r);
        else{
            return min(querymn(l, M, L, M, st[id].l), querymn(M + 1, r, M + 1, R, st[id].r));
        }
    }
    int querymx(int l, int r, int L = -1, int R = -1, int id = 0){
        if(L == -1) L = lr;
        if(R == -1) R = rr;
        //waassert(L <= l && r <= R && l <= r);
        if(l == L && r == R) return st[id].rmx();
        push(id);
        int M = (L + R) / 2;
        if(r <= M) return querymx(l, r, L, M, st[id].l);
        else if(l > M) return querymx(l, r, M + 1, R, st[id].r);
        else{
            return max(querymx(l, M, L, M, st[id].l), querymx(M + 1, r, M + 1, R, st[id].r));
        }
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, a;
    cin >> n >> a;

    SegmentTree pos, order;
    pos.init(n, 1, n);
    order.init(n, 1, n);
    pos.build();
    order.build();

    vector<int> d(n + 1);
    map<int, int, greater<>> rk;
    for(int i = 1; i <= n; i++){
        cin >> d[i];
        rk[d[i]] = i;
    }

    int l = a, r = a;
    pos.modify(a, a, 1);
    order.modify(1, 1, a);
    //printv(d, cerr);
    //printv(rk, cerr);

    for(int i = 2; i <= n; i++){
        if(r == n){
            l--;
            pos.modify(l, l, i);
            order.modify(i, i, l);
            //cerr << l << " " << i << "\n";
        }
        else if(l == 1){
            r++;
            pos.modify(r, r, i);
            order.modify(i, i, r);
            //cerr << r << " " << i << "\n";
        }
        else if(d[l - 1] < d[r + 1]){
            l--;
            pos.modify(l, l, i);
            order.modify(i, i, l);
            //cerr << l << " " << i << "\n";
        }
        else{
            r++;
            pos.modify(r, r, i);
            order.modify(i, i, r);
            //cerr << r << " " << i << "\n";
        }
    }
    //cerr << "pos ";
    //for(int i = 1; i <= n; i++) cerr << pos.querymn(i, i) << " ";
    //cerr << "\n";
    //cerr << "order ";
    //for(int i = 1; i <= n; i++) cerr << order.querymn(i, i) << " ";
    //cerr << "\n";

    int q;
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        if(c == 'F'){
            int b;
            cin >> b;
            cout << pos.querymn(b, b) - 1 << "\n";
            continue;
        }
        
        int i, e;
        cin >> i >> e;
        //cerr << "start " << i << " " << e << "\n";
        vector<int> tmp;
        for(int j = 0; j < e - 1; j++){
            tmp.eb(rk.begin()->S);
            rk.erase(rk.begin());
        }
        tmp.eb(i);
        rk.erase(d[i]);
        while(!tmp.empty()){
            d[tmp.back()] = rk.empty() ? 1 : rk.begin()->F + 1;
            rk[d[tmp.back()]] = tmp.back();
            tmp.pop_back();
        }
        //printv(rk, cerr);

        int now = i;
        int nowpos = pos.querymn(now, now);
        if(nowpos == 1) continue;

        while(true){
            int l = order.querymn(1, nowpos - 1), r = order.querymx(1, nowpos - 1);
            //cerr << "test " << now << " " << l << " " << r << "\n";
            if(now == l - 1){
                int go = n + 1;
                for(auto it = rk.begin(); it->S != now; it++){
                    if(it->S > r) go = min(go, it->S);
                }
                if(go - 1 > r){
                    pos.modify(r + 1, go - 1, nowpos, 1);
                    order.modify(nowpos, nowpos + (go - 1) - (r + 1), r + 1, 1);
                    nowpos += go - 1 - r;
                }
                pos.modify(now, now, nowpos);
                order.modify(nowpos, nowpos, now);
                nowpos++;

                if(go != n + 1) now = go;
                else if(now == 1) break;
                else{
                    pos.modify(1, now - 1, nowpos, -1);
                    order.modify(nowpos, n, now - 1, -1);
                    break;
                }
            }
            else{
                int go = 0;
                for(auto it = rk.begin(); it->S != now; it++){
                    if(it->S < l) go = max(go, it->S);
                }
                if(go + 1 < l){
                    pos.modify(go + 1, l - 1, nowpos + (l - 1) - (go + 1), -1);
                    order.modify(nowpos, nowpos + (l - 1) - (go + 1), l - 1, -1);
                    nowpos += l - 1 - go;
                }
                pos.modify(now, now, nowpos);
                order.modify(nowpos, nowpos, now);
                nowpos++;
                if(go != 0) now = go;
                else if(now == n) break;
                else{
                    pos.modify(now + 1, n, nowpos, 1);
                    order.modify(nowpos, n, now + 1, 1);
                }
            }
        }
        //cerr << "pos ";
        //for(int i = 1; i <= n; i++) cerr << pos.querymn(i, i) << " ";
        //cerr << "\n";
        //cerr << "order ";
        //for(int i = 1; i <= n; i++) cerr << order.querymn(i, i) << " ";
        //cerr << "\n";
    }

    return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 1740 KB Output isn't correct
2 Incorrect 16 ms 1868 KB Output isn't correct
3 Incorrect 11 ms 1932 KB Output isn't correct
4 Incorrect 16 ms 1928 KB Output isn't correct
5 Incorrect 43 ms 4184 KB Output isn't correct
6 Incorrect 49 ms 4316 KB Output isn't correct
7 Incorrect 60 ms 4320 KB Output isn't correct
8 Incorrect 43 ms 4340 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 184 ms 16284 KB Output isn't correct
2 Incorrect 166 ms 16364 KB Output isn't correct
3 Incorrect 179 ms 16276 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 564 ms 40432 KB Output isn't correct
6 Incorrect 508 ms 40440 KB Output isn't correct
7 Runtime error 320 ms 81744 KB Execution killed with signal 11

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 824 KB Output isn't correct
2 Incorrect 5 ms 1100 KB Output isn't correct
3 Incorrect 61 ms 8272 KB Output isn't correct
4 Incorrect 57 ms 8228 KB Output isn't correct
5 Incorrect 3 ms 588 KB Output isn't correct
6 Incorrect 126 ms 10840 KB Output isn't correct
7 Incorrect 16 ms 1868 KB Output isn't correct
8 Incorrect 180 ms 16272 KB Output isn't correct
9 Incorrect 368 ms 40340 KB Output isn't correct
10 Incorrect 3 ms 588 KB Output isn't correct
11 Incorrect 23 ms 3532 KB Output isn't correct
12 Incorrect 385 ms 32296 KB Output isn't correct
13 Incorrect 447 ms 40428 KB Output isn't correct