oj.uz

Submission #736461

# Submission time Handle Problem Language Result Execution time Memory
736461 2023-05-05T17:06:48 Z GrindMachine Cake (CEOI14_cake) C++17
0 / 100
 1080 ms 23784 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).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 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 1108 KB Output is correct
2 Incorrect 266 ms 1236 KB Output isn't correct
3 Correct 319 ms 1236 KB Output is correct
4 Correct 188 ms 1236 KB Output is correct
5 Correct 459 ms 2572 KB Output is correct
6 Incorrect 399 ms 2516 KB Output isn't correct
7 Correct 372 ms 2592 KB Output is correct
8 Correct 224 ms 2592 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 9932 KB Output is correct
2 Incorrect 82 ms 9980 KB Output isn't correct
3 Incorrect 76 ms 9920 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Correct 209 ms 22632 KB Output is correct
6 Correct 210 ms 22692 KB Output is correct
7 Incorrect 119 ms 22684 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 636 KB Output isn't correct
2 Incorrect 34 ms 860 KB Output isn't correct
3 Incorrect 84 ms 5040 KB Output isn't correct
4 Incorrect 112 ms 4972 KB Output isn't correct
5 Incorrect 145 ms 792 KB Output isn't correct
6 Incorrect 149 ms 7372 KB Output isn't correct
7 Incorrect 135 ms 1672 KB Output isn't correct
8 Correct 212 ms 9372 KB Output is correct
9 Incorrect 1060 ms 23784 KB Output isn't correct
10 Incorrect 481 ms 1484 KB Output isn't correct
11 Incorrect 630 ms 3660 KB Output isn't correct
12 Correct 1080 ms 20088 KB Output is correct
13 Correct 698 ms 23672 KB Output is correct