oj.uz

Submission #697686

# Submission time Handle Problem Language Result Execution time Memory
697686 2023-02-10T17:50:01 Z tamthegod Cake (CEOI14_cake) C++17
100 / 100
 1892 ms 23824 KB 
// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, k;
int a[maxN];
int st[4 * maxN];
void build(int id, int l, int r)
{
    if(l == r)
    {
        st[id] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}
void update(int id, int l, int r, int pos, int val)
{
    if(l == r)
    {
        st[id] = val;
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid) update(id * 2, l, mid, pos, val);
    else update(id * 2 + 1, mid + 1, r, pos, val);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v)
{
    if(l > v || r < u) return 0;
    if(l >= u && r <= v) return st[id];
    int mid = (l + r) / 2;
    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
void ReadInput()
{
    cin >> n >> k;
    vector<int> vc;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        vc.pb(a[i]);
    }
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
    for(int i=1; i<=n; i++)
        a[i] = upper_bound(vc.begin(), vc.end(), a[i]) - vc.begin();
}
void Solve()
{
    build(1, 1, n);
    set<pair<int, int>, greater<pair<int, int>>> S;
    for(int i=1; i<=n; i++)
    {
        S.insert({a[i], i});
    }
    int q;
    cin >> q;
    while(q--)
    {
        char type;
        cin >> type;
        if(type == 'E')
        {
            int i, x;
            cin >> i >> x;
            pair<int, int> tmp = {get(1, 1, n, i, i), i};
            if(S.find(tmp) != S.end()) S.erase(tmp);
            vector<pair<int, int>> bin;
            x--;
            while(x--)
            {
                auto it = S.begin();
                pair<int, int> u = *it;
                S.erase(it);
                u.fi++;
                bin.pb(u);
                update(1, 1, n, u.se, u.fi);
            }
            auto it = S.begin();
            tmp = {it->fi + 1, i};
            update(1, 1, n, tmp.se, tmp.fi);
            S.insert(tmp);
            for(auto v : bin)
                S.insert(v);
        }
        else
        {
            int i;
            cin >> i;
            int res = 0;
            if(i < k)
            {
                int tmp = get(1, 1, n, i, k - 1);
                int low = k + 1, high = n, mid;
                while(low <= high)
                {
                    mid = (low + high) / 2;
                    if(get(1, 1, n, k + 1, mid) > tmp) high = mid - 1;
                    else low = mid + 1;
                }
                res += k - i + low - k;
            }
            else
            {
                int tmp = get(1, 1, n, k + 1, i);
                int low = 1, high = k - 1, mid;
                while(low <= high)
                {
                    mid = (low + high) / 2;
                    if(get(1, 1, n, mid, k - 1) > tmp) low = mid + 1;
                    else high = mid - 1;
                }
                res += i - k + k - high;
            }
            cout << res - 1 << '\n';
        }
    }
}
int32_t main()
{
    //freopen("sol.inp", "r", stdin);
    //freopen("sol.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 23 ms 1440 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 1232 KB Output is correct
2 Correct 318 ms 1400 KB Output is correct
3 Correct 376 ms 1296 KB Output is correct
4 Correct 315 ms 1284 KB Output is correct
5 Correct 606 ms 2572 KB Output is correct
6 Correct 504 ms 2600 KB Output is correct
7 Correct 443 ms 2580 KB Output is correct
8 Correct 328 ms 2688 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 9928 KB Output is correct
2 Correct 271 ms 9888 KB Output is correct
3 Correct 303 ms 9808 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 526 ms 22724 KB Output is correct
6 Correct 624 ms 22752 KB Output is correct
7 Correct 440 ms 22628 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 716 KB Output is correct
2 Correct 83 ms 916 KB Output is correct
3 Correct 250 ms 5040 KB Output is correct
4 Correct 189 ms 5048 KB Output is correct
5 Correct 215 ms 784 KB Output is correct
6 Correct 410 ms 6552 KB Output is correct
7 Correct 300 ms 1908 KB Output is correct
8 Correct 275 ms 9424 KB Output is correct
9 Correct 1892 ms 23680 KB Output is correct
10 Correct 687 ms 1620 KB Output is correct
11 Correct 981 ms 3624 KB Output is correct
12 Correct 1707 ms 20092 KB Output is correct
13 Correct 1698 ms 23824 KB Output is correct