답안 #285910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285910 2020-08-29T18:13:18 Z caoash 케이크 (CEOI14_cake) C++14
35 / 100
2000 ms 14144 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;

unordered_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;
    vector<pi> top;
    for (int i = max(1, n - 9); i <= n; i++) {
        top.pb(mp(i, pos[i]));
    }
    while(q--) {
        char qt; cin >> qt; 
        if (qt == 'E') {
            int i, e; cin >> i >> e;
            i--;
            vector<pi> order;
            /* 
            cout << "TOP: " << '\n';
            for (int x : top) {
                cout << x << " ";
            }
            cout << '\n';
            */
            for (int j = 0; j < e - 1; j++) {
                if (top.back().s != i) {
                    int v = top.back().f; int p = top.back().s;
                    order.pb(mp(v + 1, p));
                    vals.update(0, 0, n - 1, p, v + 1);
                    d[p] = v + 1;
                }
                else {
                    j--;
                }
                top.pop_back();
            }
            int prev = d[i];
            // cout << "prev: " << prev << endl;
            d[i] = top.back().f + 1;
            vals.update(0, 0, n - 1, i, top.back().f + 1);
            order.pb(mp(top.back().f + 1, i));
            while (!top.empty()) {
                if(top.back().f != prev) order.pb(mp(top.back().f, top.back().s));
                top.pop_back(); 
            }
            reverse(all(order));
            for (pi x : order) {
                top.pb(x);
            }
            /*
            cout << "vals: " << '\n';
            for (int j = 0; j < n; j++) {
                cout << d[j] << " ";
            }
            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 + 1, 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 - 1) > best) {
                        ans = mid;
                        lo = mid + 1;
                    }
                    else {
                        hi = mid - 1;
                    }
                }
                cout << (x - ans - 1) << '\n';
            }
        }
    }
}

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 33 ms 384 KB Output is correct
5 Correct 193 ms 1024 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2085 ms 1232 KB Time limit exceeded
2 Execution timed out 2098 ms 1032 KB Time limit exceeded
3 Execution timed out 2096 ms 1144 KB Time limit exceeded
4 Correct 391 ms 896 KB Output is correct
5 Execution timed out 2090 ms 2176 KB Time limit exceeded
6 Execution timed out 2084 ms 2172 KB Time limit exceeded
7 Execution timed out 2079 ms 2168 KB Time limit exceeded
8 Correct 324 ms 1784 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 6556 KB Output is correct
2 Correct 263 ms 6428 KB Output is correct
3 Correct 279 ms 6356 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 401 ms 14144 KB Output is correct
6 Correct 467 ms 13888 KB Output is correct
7 Correct 400 ms 13628 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1182 ms 996 KB Output is correct
2 Correct 1763 ms 936 KB Output is correct
3 Execution timed out 2086 ms 3840 KB Time limit exceeded
4 Execution timed out 2084 ms 3924 KB Time limit exceeded
5 Execution timed out 2072 ms 1076 KB Time limit exceeded
6 Execution timed out 2081 ms 4848 KB Time limit exceeded
7 Execution timed out 2048 ms 1508 KB Time limit exceeded
8 Execution timed out 2086 ms 6124 KB Time limit exceeded
9 Execution timed out 2078 ms 13664 KB Time limit exceeded
10 Execution timed out 2051 ms 888 KB Time limit exceeded
11 Execution timed out 2091 ms 2148 KB Time limit exceeded
12 Execution timed out 2083 ms 11968 KB Time limit exceeded
13 Execution timed out 2086 ms 13632 KB Time limit exceeded