oj.uz

답안 #285880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285880 2020-08-29T17:19:01 Z caoash 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 30640 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--;
            int best = vals.query(0, 0, n - 1, min(x, a), max(x, a));
            if (x == a) { 
                cout << 0 << '\n';
            }
            else 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 1 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 2082 ms 5020 KB Time limit exceeded
2 Execution timed out 2082 ms 10852 KB Time limit exceeded
3 Execution timed out 2088 ms 5528 KB Time limit exceeded
4 Incorrect 413 ms 28920 KB Output isn't correct
5 Execution timed out 2079 ms 5464 KB Time limit exceeded
6 Execution timed out 2073 ms 6456 KB Time limit exceeded
7 Execution timed out 2075 ms 6080 KB Time limit exceeded
8 Incorrect 415 ms 30640 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 485 ms 9060 KB Output isn't correct
2 Incorrect 302 ms 9088 KB Output isn't correct
3 Incorrect 282 ms 8988 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 624 ms 19832 KB Output isn't correct
6 Incorrect 734 ms 19956 KB Output isn't correct
7 Incorrect 525 ms 20012 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 642 ms 2556 KB Output isn't correct
2 Incorrect 838 ms 2528 KB Output isn't correct
3 Execution timed out 2070 ms 6392 KB Time limit exceeded
4 Execution timed out 2062 ms 6524 KB Time limit exceeded
5 Incorrect 1468 ms 5544 KB Output isn't correct
6 Execution timed out 2083 ms 7256 KB Time limit exceeded
7 Execution timed out 2060 ms 4000 KB Time limit exceeded
8 Execution timed out 2073 ms 11088 KB Time limit exceeded
9 Execution timed out 2079 ms 20616 KB Time limit exceeded
10 Execution timed out 2071 ms 7932 KB Time limit exceeded
11 Execution timed out 2075 ms 4420 KB Time limit exceeded
12 Execution timed out 2091 ms 17624 KB Time limit exceeded
13 Execution timed out 2085 ms 22100 KB Time limit exceeded