oj.uz

Submission #391902

# Submission time Handle Problem Language Result Execution time Memory
391902 2021-04-20T05:45:42 Z wiwiho Cake (CEOI14_cake) C++14
75.8333 / 100
 2000 ms 54084 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);
    //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;
 
        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 + 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){
                    //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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 12 ms 464 KB Output is correct
5 Correct 48 ms 2408 KB Output is correct

Subtask #2
7.5 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1549 ms 2192 KB Output is correct
2 Correct 1173 ms 2400 KB Output is correct
3 Correct 1739 ms 2384 KB Output is correct
4 Correct 1087 ms 2388 KB Output is correct
5 Execution timed out 2080 ms 5324 KB Time limit exceeded
6 Correct 1693 ms 5496 KB Output is correct
7 Execution timed out 2076 ms 5452 KB Time limit exceeded
8 Correct 1233 ms 5504 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 21572 KB Output is correct
2 Correct 134 ms 21516 KB Output is correct
3 Correct 128 ms 21444 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 417 ms 52864 KB Output is correct
6 Correct 427 ms 52932 KB Output is correct
7 Correct 293 ms 52516 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1080 KB Output is correct
2 Correct 120 ms 1424 KB Output is correct
3 Correct 293 ms 10816 KB Output is correct
4 Correct 312 ms 10820 KB Output is correct
5 Correct 351 ms 1300 KB Output is correct
6 Correct 554 ms 14356 KB Output is correct
7 Correct 419 ms 2816 KB Output is correct
8 Correct 1081 ms 21068 KB Output is correct
9 Execution timed out 2095 ms 53420 KB Time limit exceeded
10 Correct 1148 ms 1772 KB Output is correct
11 Correct 1345 ms 5796 KB Output is correct
12 Execution timed out 2094 ms 42892 KB Time limit exceeded
13 Correct 1958 ms 54084 KB Output is correct