oj.uz

답안 #285888

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285888 2020-08-29T17:23:06 Z caoash 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 25336 KB 
#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

template<class T, int SZ> struct Seg{
    T tree[4*SZ];
    T merge(T a, T b){
        return max(a, b);
    }
    
    void update(int v, int l, int r, int i, T x) {
        if (i > r || i < l) {
            return;
        } else if (l == r) {
            tree[v] = x;
        } else {
            int m = (l + r) / 2;
            update(2 * v + 1, l, m, i, x);
            update(2 * v + 2, m + 1, r, i, x);
            tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
        }
    }

    T query(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) {
            return 0;
        } else if (l >= ql && r <= qr) {
            return tree[v];
        } else {
            int m = (l + r) / 2;
            T a = query(2 * v + 1, l, m, ql, qr);
            T b = query(2 * v + 2, m + 1, r, ql, qr);
            return merge(a,b);
        }
    }
};

const int MX = 200005;

map<int, int> pos;

Seg<int, MX> vals; 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a; cin >> n >> a;
    a--;
    vi d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i]; 
        pos[d[i]] = i;
        vals.update(0, 0, n - 1, i, d[i]);
    }
    /*
    cout << "vals: " << '\n';
    for (int i = 0; i < n; i++) {
        cout << vals.query(0, 0, n - 1, i, i) << " ";
    }
    cout << '\n';
    */ 
    int q; cin >> q;
    vi top;
    for (int i = max(1, n - 9); i <= n; i++) {
        top.pb(i);
    }
    while(q--) {
        char qt; cin >> qt; 
        if (qt == 'E') {
            int i, e; cin >> i >> e;
            i--;
            vi order;
            /*
            cout << "TOP: " << endl;
            for (int x : top) {
                cout << x << " ";
            }
            */ 
            for (int i = 0; i < e - 1; i++) {
                order.pb(top.back() + 1);
                vals.update(0, 0, n - 1, pos[top.back()], top.back() + 1);
                d[pos[top.back()]] = top.back() + 1;
                pos[top.back() + 1] = pos[top.back()];
                top.pop_back();
            }
            int prev = d[i];
            // cout << "prev: " << prev << endl;
            d[i] = top.back() + 1;
            vals.update(0, 0, n - 1, i, top.back() + 1);
            order.pb(top.back() + 1);
            pos[top.back() + 1] = i;
            while (!top.empty()) {
                if(top.back() != prev) order.pb(top.back());
                top.pop_back(); 
            }
            reverse(all(order));
            for (int x : order) {
                top.pb(x);
            }
            /*
            cout << "vals: " << '\n';
            for (int i = 0; i < n; i++) {
                cout << d[i] << " ";
            }
            cout << '\n';
            */
        }
        else {
            int x; cin >> x;
            x--;
            if (x == a) { 
                cout << 0 << '\n';
                continue;
            }
            int best = 0;
            if (x < a) best = vals.query(0, 0, n - 1, x, a - 1);
            else if (x > a) best = vals.query(0, 0, n - 1, a + 1, x);
            if (x < a) {
                int lo = a + 1; int hi = n - 1;
                int ans = n;
                while (lo <= hi) {
                    int mid = (lo + hi) / 2;
                    if (vals.query(0, 0, n - 1, a, mid) > best) {
                        ans = mid;
                        hi = mid - 1;
                    }
                    else {
                        lo = mid + 1;
                    }
                }
                cout << (ans - x - 1) << '\n';
            }
            else {
                int lo = 0; int hi = a - 1;
                int ans = -1;
                while (lo <= hi) {
                    int mid = (lo + hi) / 2;
                    if (vals.query(0, 0, n - 1, mid, a) > best) {
                        ans = mid;
                        lo = mid + 1;
                    }
                    else {
                        hi = mid - 1;
                    }
                }
                cout << (x - ans - 1) << '\n';
            }
        }
    }
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2076 ms 3772 KB Time limit exceeded
2 Execution timed out 2068 ms 9164 KB Time limit exceeded
3 Execution timed out 2084 ms 4472 KB Time limit exceeded
4 Correct 393 ms 24440 KB Output is correct
5 Execution timed out 2091 ms 4560 KB Time limit exceeded
6 Execution timed out 2066 ms 5212 KB Time limit exceeded
7 Execution timed out 2084 ms 5544 KB Time limit exceeded
8 Correct 423 ms 25336 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 7032 KB Output is correct
2 Incorrect 282 ms 6904 KB Output isn't correct
3 Incorrect 277 ms 6648 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Correct 527 ms 15740 KB Output is correct
6 Incorrect 667 ms 15864 KB Output isn't correct
7 Incorrect 416 ms 15352 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 624 ms 1908 KB Output isn't correct
2 Incorrect 846 ms 2116 KB Output isn't correct
3 Execution timed out 2070 ms 5832 KB Time limit exceeded
4 Execution timed out 2081 ms 5112 KB Time limit exceeded
5 Incorrect 1488 ms 4360 KB Output isn't correct
6 Execution timed out 2079 ms 5948 KB Time limit exceeded
7 Execution timed out 2083 ms 3284 KB Time limit exceeded
8 Execution timed out 2085 ms 9076 KB Time limit exceeded
9 Execution timed out 2033 ms 16804 KB Time limit exceeded
10 Execution timed out 2081 ms 6140 KB Time limit exceeded
11 Execution timed out 2089 ms 3448 KB Time limit exceeded
12 Execution timed out 2053 ms 14188 KB Time limit exceeded
13 Execution timed out 2079 ms 17936 KB Time limit exceeded