oj.uz

답안 #736467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736467 2023-05-05T17:16:22 Z GrindMachine 케이크 (CEOI14_cake) C++17
30 / 100
 2000 ms 22300 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    /*=======================================================*/

    struct data {
        ll a;
    };

    data neutral = { -inf2};

    void merge(data &curr, data &left, data &right) {
        curr.a = max(left.a, right.a);
    }

    void create(int x, int lx, int rx, T v) {
        tr[x].a = v;
    }

    void modify(int x, int lx, int rx, T v) {
        tr[x].a = v;
    }

    /*=======================================================*/

    int siz = 1;
    vector<data> tr;

    segtree(int n) {
        init(n);
    }

    segtree() {

    };

    void init(int n) {
        while (siz < n) siz *= 2;
        tr.assign(2 * siz, neutral);
    }

    void build(vector<T> &a, int n, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < n) {
                create(x, lx, rx, a[lx]);
            }

            return;
        }

        int mid = (lx + rx) / 2;

        build(a, n, 2 * x + 1, lx, mid);
        build(a, n, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void build(vector<T> &a, int n) {
        build(a, n, 0, 0, siz);
    }

    void pupd(int i, T v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            modify(x, lx, rx, v);
            return;
        }

        int mid = (lx + rx) / 2;

        if (i < mid) {
            pupd(i, v, 2 * x + 1, lx, mid);
        }
        else {
            pupd(i, v, 2 * x + 2, mid, rx);
        }

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void pupd(int i, T v) {
        pupd(i, v, 0, 0, siz);
    }

    data query(int l, int r, int x, int lx, int rx) {
        if (lx >= r or rx <= l) return neutral;
        if (lx >= l and rx <= r) return tr[x];

        int mid = (lx + rx) / 2;

        data curr;
        data left = query(l, r, 2 * x + 1, lx, mid);
        data right = query(l, r, 2 * x + 2, mid, rx);

        merge(curr, left, right);
        return curr;
    }

    data query(int l, int r) {
        return query(l, r + 1, 0, 0, siz);
    }

    int closest_right(int l, ll mx, int x, int lx, int rx) {
        if (rx <= l) return -1;
        if (tr[x].a < mx) return -1;
        if (rx - lx == 1) return lx;

        int mid = (lx + rx) >> 1;

        int res = closest_right(l, mx, 2 * x + 1, lx, mid);

        if (res == -1) {
            res = closest_right(l, mx, 2 * x + 2, mid, rx);
        }

        return res;
    }

    int closest_right(int l, ll mx) {
        return closest_right(l, mx, 0, 0, siz);
    }

    int closest_left(int r, ll mx, int x, int lx, int rx) {
        if (lx > r) return -1;
        if (tr[x].a < mx) return -1;
        if (rx - lx == 1) return lx;

        int mid = (lx + rx) >> 1;

        int res = closest_left(r, mx, 2 * x + 2, mid, rx);

        if (res == -1) {
            res = closest_left(r, mx, 2 * x + 1, lx, mid);
        }

        return res;
    }

    int closest_left(int r, ll mx) {
        return closest_left(r, mx, 0, 0, siz);
    }
};

void solve(int test_case)
{
    ll n; cin >> n;
    ll s; cin >> s;
    vector<ll> a(n + 5);
    rep1(i, n) cin >> a[i];

    set<pll, greater<pll>> st;
    rep1(i, n) st.insert({a[i], i});

    segtree<ll> seg(n + 5);
    a[0] = a[n + 1] = inf2;
    seg.build(a, n + 2);

    ll q; cin >> q;

    while (q--) {
        char ch; cin >> ch;
        if (ch == 'E') {
            ll i, k; cin >> i >> k;
            st.erase({a[i], i});
            ll cnt = 0;
            ll v = st.begin()->first + 1;
            vector<pll> vals;
            bool flag = true;

            for (auto it = st.begin(); it != st.end(); ++it) {
                cnt++;
                if (cnt < k) {
                    vals.pb(*it);
                    v = it->first - 1;
                }
                else {
                    if (v == it->first) {
                        flag = false;
                    }
                    break;
                }
            }

            if (!flag) {
                trav(p, vals) {
                    a[p.ss]++;
                    st.erase(p);
                    st.insert({p.ff + 1, p.ss});
                    seg.pupd(p.ss, p.ff + 1);
                }

                v++;
            }

            st.insert({v, i});
            seg.pupd(i, v);
            a[i] = v;
        }
        else {
            ll i; cin >> i;
            if (i == s) {
                cout << 0 << endl;
            }
            else {
                ll l = s, r = s;
                ll ans = 0;

                while (true) {
                    if (l == i or r == i) break;
                    ans++;
                    if (a[l - 1] < a[r + 1]) {
                        l--;
                    }
                    else {
                        r++;
                    }
                }

                cout << ans << endl;
            }

            // else if (i < s) {
            //     ll mx = seg.query(i, s).a;
            //     ll pos = seg.closest_right(s + 1, mx) - 1;
            //     ll ans = pos - i;
            //     cout << ans << endl;
            // }
            // else {
            //     ll mx = seg.query(s, i).a;
            //     ll pos = seg.closest_left(s - 1, mx) + 1;
            //     ll ans = i - pos;
            //     cout << ans << endl;
            // }
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 9 ms 452 KB Output is correct
5 Correct 90 ms 1408 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 432 ms 1108 KB Output is correct
2 Correct 261 ms 1236 KB Output is correct
3 Correct 329 ms 1236 KB Output is correct
4 Correct 199 ms 1356 KB Output is correct
5 Correct 458 ms 2568 KB Output is correct
6 Correct 408 ms 2592 KB Output is correct
7 Correct 352 ms 2592 KB Output is correct
8 Correct 236 ms 2516 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2058 ms 9584 KB Time limit exceeded
2 Execution timed out 2060 ms 9700 KB Time limit exceeded
3 Execution timed out 2062 ms 9696 KB Time limit exceeded
4 Correct 0 ms 212 KB Output is correct
5 Execution timed out 2071 ms 22272 KB Time limit exceeded
6 Execution timed out 2070 ms 22160 KB Time limit exceeded
7 Execution timed out 2072 ms 22244 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 596 KB Output is correct
2 Correct 221 ms 820 KB Output is correct
3 Execution timed out 2055 ms 5108 KB Time limit exceeded
4 Execution timed out 2066 ms 5420 KB Time limit exceeded
5 Correct 347 ms 824 KB Output is correct
6 Execution timed out 2084 ms 7164 KB Time limit exceeded
7 Correct 1577 ms 1876 KB Output is correct
8 Correct 505 ms 9436 KB Output is correct
9 Execution timed out 2079 ms 22300 KB Time limit exceeded
10 Correct 1168 ms 1620 KB Output is correct
11 Execution timed out 2086 ms 2504 KB Time limit exceeded
12 Execution timed out 2084 ms 18688 KB Time limit exceeded
13 Execution timed out 2069 ms 22244 KB Time limit exceeded