oj.uz

답안 #391884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391884 2021-04-20T04:32:02 Z wiwiho 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 81888 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 << ')';
}
bool assertflag = false;
 
void waassert(bool t){
    if(!assertflag || 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 n, a;
void assertrange(int l, int r){
    waassert(l <= r && 1 <= l && r <= n);
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    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;
        assertflag = true;
        waassert(nowpos != 0);
        assertflag = false;
 
        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){
                    //assertrange(r + 1, go - 1);
                    //assertrange(nowpos, nowpos + (go - 1) - (r + 1));
                    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){
                    //assertrange(go + 1, l - 1);
                    //assertrange(nowpos, nowpos + (l - 1) - (go + 1));
                    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);
                    break;
                }
            }
        }
        //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 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 3416 KB Execution killed with signal 11
2 Runtime error 12 ms 3664 KB Execution killed with signal 11
3 Runtime error 12 ms 3660 KB Execution killed with signal 11
4 Incorrect 1299 ms 1916 KB Output isn't correct
5 Runtime error 28 ms 8360 KB Execution killed with signal 11
6 Runtime error 26 ms 8560 KB Execution killed with signal 11
7 Runtime error 55 ms 8556 KB Execution killed with signal 11
8 Incorrect 1433 ms 4340 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 127 ms 33000 KB Execution killed with signal 11
2 Runtime error 134 ms 33220 KB Execution killed with signal 11
3 Runtime error 124 ms 33244 KB Execution killed with signal 11
4 Correct 0 ms 208 KB Output is correct
5 Correct 405 ms 41044 KB Output is correct
6 Runtime error 378 ms 81824 KB Execution killed with signal 11
7 Runtime error 291 ms 81784 KB Execution killed with signal 11

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 1356 KB Execution killed with signal 11
2 Runtime error 6 ms 2020 KB Execution killed with signal 11
3 Runtime error 61 ms 16724 KB Execution killed with signal 11
4 Runtime error 54 ms 16656 KB Execution killed with signal 11
5 Runtime error 3 ms 1100 KB Execution killed with signal 11
6 Runtime error 83 ms 21760 KB Execution killed with signal 11
7 Runtime error 11 ms 3788 KB Execution killed with signal 11
8 Correct 1197 ms 16368 KB Output is correct
9 Runtime error 380 ms 81888 KB Execution killed with signal 11
10 Runtime error 3 ms 1100 KB Execution killed with signal 11
11 Runtime error 22 ms 6864 KB Execution killed with signal 11
12 Runtime error 279 ms 65476 KB Execution killed with signal 11
13 Execution timed out 2096 ms 42036 KB Time limit exceeded