oj.uz

답안 #391818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391818 2021-04-20T03:18:41 Z wiwiho 케이크 (CEOI14_cake) C++14
0 / 100
 1515 ms 1048580 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 << ')';
}

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";
        //assert(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;
        //assert(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;
        //assert(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 Runtime error 1515 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 3392 KB Execution killed with signal 11
2 Runtime error 19 ms 3660 KB Execution killed with signal 11
3 Runtime error 12 ms 3660 KB Execution killed with signal 11
4 Runtime error 19 ms 3660 KB Execution killed with signal 11
5 Runtime error 45 ms 8364 KB Execution killed with signal 11
6 Runtime error 61 ms 8540 KB Execution killed with signal 11
7 Runtime error 54 ms 8556 KB Execution killed with signal 11
8 Runtime error 48 ms 8512 KB Execution killed with signal 11

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 192 ms 33040 KB Execution killed with signal 11
2 Runtime error 178 ms 32996 KB Execution killed with signal 11
3 Runtime error 183 ms 32996 KB Execution killed with signal 11
4 Runtime error 641 ms 1048580 KB Execution killed with signal 9
5 Runtime error 607 ms 81732 KB Execution killed with signal 11
6 Runtime error 544 ms 81804 KB Execution killed with signal 11
7 Runtime error 309 ms 81684 KB Execution killed with signal 11

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 1464 KB Execution killed with signal 11
2 Runtime error 7 ms 2032 KB Execution killed with signal 11
3 Runtime error 69 ms 16624 KB Execution killed with signal 11
4 Runtime error 75 ms 16656 KB Execution killed with signal 11
5 Runtime error 3 ms 1100 KB Execution killed with signal 11
6 Runtime error 134 ms 21716 KB Execution killed with signal 11
7 Runtime error 17 ms 3728 KB Execution killed with signal 11
8 Runtime error 208 ms 32980 KB Execution killed with signal 11
9 Runtime error 408 ms 81868 KB Execution killed with signal 11
10 Runtime error 6 ms 1080 KB Execution killed with signal 11
11 Runtime error 27 ms 6972 KB Execution killed with signal 11
12 Runtime error 350 ms 65524 KB Execution killed with signal 11
13 Runtime error 494 ms 81736 KB Execution killed with signal 11