oj.uz

Submission #736460

# Submission time Handle Problem Language Result Execution time Memory
736460 2023-05-05T17:05:09 Z GrindMachine Cake (CEOI14_cake) C++17
0 / 100
 1151 ms 24012 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 = inf1;
            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).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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 1440 KB Output is correct
2 Incorrect 298 ms 1524 KB Output isn't correct
3 Correct 334 ms 1492 KB Output is correct
4 Incorrect 216 ms 1492 KB Output isn't correct
5 Correct 477 ms 2816 KB Output is correct
6 Incorrect 443 ms 2844 KB Output isn't correct
7 Correct 357 ms 2852 KB Output is correct
8 Incorrect 219 ms 2852 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 10160 KB Output is correct
2 Incorrect 75 ms 10164 KB Output isn't correct
3 Incorrect 68 ms 10352 KB Output isn't correct
4 Incorrect 1 ms 316 KB Output isn't correct
5 Correct 214 ms 22880 KB Output is correct
6 Correct 203 ms 22936 KB Output is correct
7 Incorrect 115 ms 22944 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 1064 KB Output isn't correct
2 Incorrect 34 ms 1084 KB Output isn't correct
3 Incorrect 82 ms 5292 KB Output isn't correct
4 Incorrect 119 ms 5232 KB Output isn't correct
5 Incorrect 146 ms 1072 KB Output isn't correct
6 Incorrect 164 ms 7652 KB Output isn't correct
7 Incorrect 145 ms 1976 KB Output isn't correct
8 Correct 231 ms 9688 KB Output is correct
9 Incorrect 1151 ms 24012 KB Output isn't correct
10 Incorrect 481 ms 1776 KB Output isn't correct
11 Incorrect 640 ms 3840 KB Output isn't correct
12 Correct 1093 ms 20296 KB Output is correct
13 Correct 710 ms 23932 KB Output is correct