oj.uz

Submission #391904

# Submission time Handle Problem Language Result Execution time Memory
391904 2021-04-20T05:57:08 Z wiwiho Cake (CEOI14_cake) C++14
75.8333 / 100
 2000 ms 53872 KB 
#pragma GCC optimize("Ofast")
 
#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 336 KB Output is correct
4 Correct 15 ms 528 KB Output is correct
5 Correct 36 ms 2404 KB Output is correct

Subtask #2
7.5 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1589 ms 2180 KB Output is correct
2 Correct 1206 ms 2388 KB Output is correct
3 Correct 1686 ms 2500 KB Output is correct
4 Correct 1111 ms 2380 KB Output is correct
5 Execution timed out 2095 ms 5324 KB Time limit exceeded
6 Correct 1683 ms 5512 KB Output is correct
7 Execution timed out 2078 ms 5452 KB Time limit exceeded
8 Correct 1249 ms 5496 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 21568 KB Output is correct
2 Correct 131 ms 21440 KB Output is correct
3 Correct 124 ms 21448 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 400 ms 52764 KB Output is correct
6 Correct 398 ms 52812 KB Output is correct
7 Correct 321 ms 52568 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 972 KB Output is correct
2 Correct 117 ms 1436 KB Output is correct
3 Correct 318 ms 10896 KB Output is correct
4 Correct 304 ms 11048 KB Output is correct
5 Correct 334 ms 964 KB Output is correct
6 Correct 501 ms 14408 KB Output is correct
7 Correct 409 ms 2812 KB Output is correct
8 Correct 1061 ms 21188 KB Output is correct
9 Execution timed out 2087 ms 53444 KB Time limit exceeded
10 Correct 1122 ms 1904 KB Output is correct
11 Correct 1316 ms 5836 KB Output is correct
12 Execution timed out 2061 ms 42932 KB Time limit exceeded
13 Correct 1990 ms 53872 KB Output is correct