oj.uz

답안 #736470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736470 2023-05-05T17:29:56 Z GrindMachine 케이크 (CEOI14_cake) C++17
100 / 100
 1119 ms 23768 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 if (i < s) {
                ll mx = seg.query(i, s - 1).a;
                ll pos = seg.closest_right(s + 1, mx) - 1;
                ll ans = pos - i;
                cout << ans << endl;
            }
            else {
                ll mx = seg.query(s + 1, 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 5 ms 340 KB Output is correct
5 Correct 15 ms 1316 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 1108 KB Output is correct
2 Correct 280 ms 1236 KB Output is correct
3 Correct 367 ms 1236 KB Output is correct
4 Correct 196 ms 1280 KB Output is correct
5 Correct 488 ms 2568 KB Output is correct
6 Correct 406 ms 2592 KB Output is correct
7 Correct 403 ms 2592 KB Output is correct
8 Correct 220 ms 2596 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 9944 KB Output is correct
2 Correct 88 ms 9788 KB Output is correct
3 Correct 61 ms 9808 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 218 ms 22632 KB Output is correct
6 Correct 228 ms 22708 KB Output is correct
7 Correct 100 ms 22452 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 596 KB Output is correct
2 Correct 36 ms 920 KB Output is correct
3 Correct 88 ms 5084 KB Output is correct
4 Correct 111 ms 5084 KB Output is correct
5 Correct 144 ms 780 KB Output is correct
6 Correct 153 ms 7408 KB Output is correct
7 Correct 139 ms 1716 KB Output is correct
8 Correct 226 ms 9428 KB Output is correct
9 Correct 1119 ms 23588 KB Output is correct
10 Correct 516 ms 1476 KB Output is correct
11 Correct 658 ms 3572 KB Output is correct
12 Correct 1047 ms 20188 KB Output is correct
13 Correct 720 ms 23768 KB Output is correct