oj.uz

Submission #391989

# Submission time Handle Problem Language Result Execution time Memory
391989 2021-04-20T09:25:24 Z wiwiho Cake (CEOI14_cake) C++14
75.8333 / 100
 2000 ms 97784 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";\
}
#define int int_fast32_t

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 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(4 * n);
        lr = _lr;
        rr = _rr;
    }

    void push(int id){
        if(st[id].tag == -1) return;
        int lc = 2 * id + 1, rc = 2 * id + 2;
        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;
    }

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

    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, 2 * id + 1);
        else if(l > M) modify(l, r, f, d, M + 1, R, 2 * id + 2);
        else{
            modify(l, M, f, d, L, M, 2 * id + 1);
            modify(M + 1, r, f + d * (M + 1 - l), d, M + 1, R, 2 * id + 2);
        }
        st[id].mn = min(st[2 * id + 1].rmn(), st[2 * id + 2].rmn());
        st[id].mx = max(st[2 * id + 1].rmx(), st[2 * id + 2].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, 2 * id + 1);
        else if(l > M) return querymn(l, r, M + 1, R, 2 * id + 2);
        else{
            return min(querymn(l, M, L, M, 2 * id + 1), querymn(M + 1, r, M + 1, R, 2 * id + 2));
        }
    }
    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, 2 * id + 1);
        else if(l > M) return querymx(l, r, M + 1, R, 2 * id + 2);
        else{
            return max(querymx(l, M, L, M, 2 * id + 1), querymx(M + 1, r, M + 1, R, 2 * id + 2));
        }
    }
};

int n, a;
void assertrange(int l, int r){
    waassert(l <= r && 1 <= l && r <= n);
}

signed 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);

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

    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;
        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();
        }

        int now = i;
        int nowpos = pos.querymn(now, now);
        if(nowpos == 1) continue;
        int l = order.querymn(1, nowpos - 1), r = order.querymx(1, nowpos - 1);

        while(true){
            //cerr << "test " << l << " " << r << " " << now << "\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++;
                r = go - 1;
                l = now;

                if(go != n + 1) now = go;
                else if(now == 1) break;
                else{
                    pos.modify(1, now - 1, nowpos + now - 2, -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++;
                l = go + 1;
                r = now;
                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;
                }
            }
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 12 ms 716 KB Output is correct
5 Correct 38 ms 4172 KB Output is correct

Subtask #2
7.5 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1545 ms 3788 KB Output is correct
2 Correct 1225 ms 4160 KB Output is correct
3 Correct 1679 ms 4044 KB Output is correct
4 Correct 1187 ms 4144 KB Output is correct
5 Execution timed out 2093 ms 9676 KB Time limit exceeded
6 Correct 1667 ms 9916 KB Output is correct
7 Execution timed out 2097 ms 9804 KB Time limit exceeded
8 Correct 1294 ms 9900 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 39240 KB Output is correct
2 Correct 162 ms 39072 KB Output is correct
3 Correct 134 ms 39108 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 461 ms 96848 KB Output is correct
6 Correct 437 ms 96840 KB Output is correct
7 Correct 301 ms 96708 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1484 KB Output is correct
2 Correct 116 ms 2276 KB Output is correct
3 Correct 315 ms 19664 KB Output is correct
4 Correct 314 ms 19592 KB Output is correct
5 Correct 345 ms 1396 KB Output is correct
6 Correct 523 ms 25892 KB Output is correct
7 Correct 418 ms 4556 KB Output is correct
8 Correct 1082 ms 38672 KB Output is correct
9 Execution timed out 2047 ms 97488 KB Time limit exceeded
10 Correct 1129 ms 2120 KB Output is correct
11 Correct 1407 ms 9276 KB Output is correct
12 Execution timed out 2100 ms 78164 KB Time limit exceeded
13 Execution timed out 2015 ms 97784 KB Time limit exceeded