oj.uz

Submission #391906

# Submission time Handle Problem Language Result Execution time Memory
391906 2021-04-20T05:59:16 Z wiwiho Cake (CEOI14_cake) C++14
75.8333 / 100
 2000 ms 53748 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 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);
}
 
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);
 
    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 11 ms 460 KB Output is correct
5 Correct 38 ms 2424 KB Output is correct

Subtask #2
7.5 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 2184 KB Output is correct
2 Correct 1222 ms 2500 KB Output is correct
3 Correct 1686 ms 2392 KB Output is correct
4 Correct 1158 ms 2380 KB Output is correct
5 Execution timed out 2084 ms 5324 KB Time limit exceeded
6 Correct 1660 ms 5492 KB Output is correct
7 Execution timed out 2089 ms 5516 KB Time limit exceeded
8 Correct 1279 ms 5496 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 21600 KB Output is correct
2 Correct 141 ms 21516 KB Output is correct
3 Correct 124 ms 21444 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 404 ms 52804 KB Output is correct
6 Correct 438 ms 52768 KB Output is correct
7 Correct 282 ms 52544 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 976 KB Output is correct
2 Correct 115 ms 1380 KB Output is correct
3 Correct 291 ms 10836 KB Output is correct
4 Correct 302 ms 10816 KB Output is correct
5 Correct 350 ms 1128 KB Output is correct
6 Correct 540 ms 14268 KB Output is correct
7 Correct 419 ms 2928 KB Output is correct
8 Correct 1073 ms 21072 KB Output is correct
9 Execution timed out 2099 ms 53340 KB Time limit exceeded
10 Correct 1104 ms 1860 KB Output is correct
11 Correct 1274 ms 5956 KB Output is correct
12 Execution timed out 2084 ms 43068 KB Time limit exceeded
13 Correct 1897 ms 53748 KB Output is correct