oj.uz

답안 #391822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391822 2021-04-20T03:21:22 Z wiwiho 케이크 (CEOI14_cake) C++14
0 / 100
 551 ms 40456 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 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 1868 KB Output isn't correct
2 Incorrect 16 ms 1868 KB Output isn't correct
3 Incorrect 11 ms 1928 KB Output isn't correct
4 Incorrect 16 ms 1932 KB Output isn't correct
5 Incorrect 40 ms 4252 KB Output isn't correct
6 Incorrect 42 ms 4320 KB Output isn't correct
7 Incorrect 52 ms 4312 KB Output isn't correct
8 Incorrect 42 ms 4324 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 208 ms 16268 KB Output isn't correct
2 Incorrect 168 ms 16364 KB Output isn't correct
3 Incorrect 166 ms 16452 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 551 ms 40436 KB Output isn't correct
6 Incorrect 538 ms 40456 KB Output isn't correct
7 Incorrect 267 ms 40380 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 716 KB Output isn't correct
2 Incorrect 6 ms 1072 KB Output isn't correct
3 Incorrect 68 ms 8340 KB Output isn't correct
4 Incorrect 52 ms 8292 KB Output isn't correct
5 Incorrect 2 ms 588 KB Output isn't correct
6 Incorrect 126 ms 10820 KB Output isn't correct
7 Incorrect 15 ms 1868 KB Output isn't correct
8 Incorrect 165 ms 16360 KB Output isn't correct
9 Incorrect 372 ms 40360 KB Output isn't correct
10 Incorrect 3 ms 588 KB Output isn't correct
11 Incorrect 23 ms 3476 KB Output isn't correct
12 Incorrect 389 ms 32408 KB Output isn't correct
13 Incorrect 482 ms 40340 KB Output isn't correct