oj.uz

답안 #391883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391883 2021-04-20T04:31:10 Z wiwiho 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 81860 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 > 1 || 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 Execution timed out 2085 ms 204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 3404 KB Execution killed with signal 11
2 Runtime error 12 ms 3596 KB Execution killed with signal 11
3 Runtime error 11 ms 3612 KB Execution killed with signal 11
4 Incorrect 1289 ms 1912 KB Output isn't correct
5 Runtime error 28 ms 8396 KB Execution killed with signal 11
6 Incorrect 21 ms 4292 KB Output isn't correct
7 Runtime error 54 ms 8544 KB Execution killed with signal 11
8 Incorrect 1419 ms 4328 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 32968 KB Execution killed with signal 11
2 Runtime error 133 ms 33260 KB Execution killed with signal 11
3 Runtime error 132 ms 33168 KB Execution killed with signal 11
4 Correct 1 ms 204 KB Output is correct
5 Correct 426 ms 41076 KB Output is correct
6 Runtime error 363 ms 81860 KB Execution killed with signal 11
7 Incorrect 249 ms 40484 KB Output isn't correct

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 1996 KB Execution killed with signal 11
3 Runtime error 60 ms 16688 KB Execution killed with signal 11
4 Runtime error 53 ms 16660 KB Execution killed with signal 11
5 Runtime error 3 ms 1100 KB Execution killed with signal 11
6 Runtime error 82 ms 21768 KB Execution killed with signal 11
7 Runtime error 11 ms 3660 KB Execution killed with signal 11
8 Correct 1214 ms 16488 KB Output is correct
9 Runtime error 363 ms 81772 KB Execution killed with signal 11
10 Runtime error 3 ms 1100 KB Execution killed with signal 11
11 Runtime error 22 ms 6988 KB Execution killed with signal 11
12 Runtime error 281 ms 65496 KB Execution killed with signal 11
13 Execution timed out 2081 ms 41968 KB Time limit exceeded