Submission #90821

#	Time	Username	Problem	Language	Result	Execution time	Memory
90821		EntityIT	Cake (CEOI14_cake)	C++14	100 / 100	370 ms	6728 KiB

cake

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define fi first
#define se second
typedef pair<int, int> ii;

const int N = 250005, inf = 1e9 + 123;
int n, start, q, cur;
ii pos[11];
vector<int> a[2];

struct It {
    int node[N << 2];
    void build_tree (bool _, int nd, int Left, int Right) {
        if (Left == Right) {
            node[nd] = a[_][Left];
            return ;
        }
        int mid = Left + Right >> 1;
        build_tree(_, nd << 1, Left, mid); build_tree(_, nd << 1 | 1, mid + 1, Right);
        node[nd] = max(node[nd << 1], node[nd << 1 | 1]);
    }
    void update (int nd, int Left, int Right, int pos, int val) {
        if (pos < Left || Right < pos) return ;
        if (Left == Right) { node[nd] = val; return ; }
        int mid = Left + Right >> 1;
        update(nd << 1, Left, mid, pos, val); update(nd << 1 | 1, mid + 1, Right, pos, val);
        node[nd] = max(node[nd << 1], node[nd << 1 | 1]);
    }
    int get (int nd, int Left, int Right, int l, int r) {
//        cout << "l = " << l << "  r = " << r << '\n';
        if (Right < l || r < Left) return 0;
        if (l <= Left && Right <= r) return node[nd];
        int mid = Left + Right >> 1;
        return max(get(nd << 1, Left, mid, l, r), get(nd << 1 | 1, mid + 1, Right, l, r) );
    }
    int getPos (int nd, int Left, int Right, int val) {
        if (Left == Right) return Left;
        int mid = Left + Right >> 1;
        if (node[nd << 1] > val) return getPos(nd << 1, Left, mid, val);
        else return getPos(nd << 1 | 1, mid + 1, Right, val);
    }
} it[2];

ii getRealPos (int b) {
    if (b == start) return ii(-1, -1);
    if (b > start) return ii(1, b - start - 1);
    return ii(0, start - b - 1);
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("cake.in", "r", stdin);
    cin >> n >> start; cur = n;
    for (int i = 1; i <= n; ++i) {
        int inp; cin >> inp;
        if (n - inp + 1 <= 10) pos[n - inp + 1] = getRealPos(i);
        if (i < start) a[0].pb(inp);
        else if (i > start) a[1].pb(inp);
    }
    reverse(a[0].begin(), a[0].end() );
    a[0].pb(inf);
    a[1].pb(inf);

//    for (auto _ : a[0]) cout << _ << ' '; cout << '\n';
//    for (auto _ : a[1]) cout << _ << ' '; cout << '\n';
//    for (int i = 1; i <= min(10, n); ++i) cout << pos[i].fi << '-' << pos[i].se << ' '; cout << '\n';

    it[0].build_tree(0, 1, 0, (int)a[0].size() - 1);
    it[1].build_tree(1, 1, 0, (int)a[1].size() - 1);

    cin >> q;

    while (q --) {
        char c; int b; cin >> c >> b;
        ii realPos = getRealPos(b);
        if (c == 'F') {
            if (realPos == ii(-1, -1) ) cout << "0\n";
            else cout << realPos.se +
                it[realPos.fi ^ 1].getPos(1, 0, (int)a[realPos.fi ^ 1].size() - 1,
                                                                it[realPos.fi].get(1, 0, (int)a[realPos.fi].size() - 1, 0, realPos.se) ) + 1 << '\n';
        }
        else {
            int e; cin >> e;

            int ran = 10;
            for (int i = 10; i > e; --i) if (pos[i] == realPos) ran = i;

            for (int i = ran; i > e; --i) pos[i] = pos[i - 1];
            pos[e] = realPos;
            for (int i = e; i > 0; --i) {
                ++cur;
                if (pos[i].fi == -1) continue ;
                it[ pos[i].fi ].update(1, 0, (int)a[ pos[i].fi ].size() - 1, pos[i].se, cur);
            }
        }
    }

    return 0;
}

Compilation message (stderr)

cake.cpp: In member function 'void It::build_tree(bool, int, int, int)':
cake.cpp:22:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = Left + Right >> 1;
                   ~~~~~^~~~~~~
cake.cpp: In member function 'void It::update(int, int, int, int, int)':
cake.cpp:29:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = Left + Right >> 1;
                   ~~~~~^~~~~~~
cake.cpp: In member function 'int It::get(int, int, int, int, int)':
cake.cpp:37:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = Left + Right >> 1;
                   ~~~~~^~~~~~~
cake.cpp: In member function 'int It::getPos(int, int, int, int)':
cake.cpp:42:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = Left + Right >> 1;
                   ~~~~~^~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50