oj.uz

Submission #697676

# Submission time Handle Problem Language Result Execution time Memory
697676 2023-02-10T17:26:32 Z tamthegod Cake (CEOI14_cake) C++17
0 / 100
 1791 ms 23732 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;
            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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 626 ms 5328 KB Output isn't correct
2 Incorrect 384 ms 1292 KB Output isn't correct
3 Incorrect 442 ms 1300 KB Output isn't correct
4 Incorrect 393 ms 1404 KB Output isn't correct
5 Incorrect 680 ms 3852 KB Output isn't correct
6 Incorrect 591 ms 2600 KB Output isn't correct
7 Incorrect 501 ms 2616 KB Output isn't correct
8 Incorrect 444 ms 2604 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 426 ms 9908 KB Output isn't correct
2 Incorrect 270 ms 9872 KB Output isn't correct
3 Incorrect 277 ms 9728 KB Output isn't correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 505 ms 22812 KB Output isn't correct
6 Incorrect 613 ms 22796 KB Output isn't correct
7 Incorrect 439 ms 22464 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 712 KB Output isn't correct
2 Incorrect 84 ms 888 KB Output isn't correct
3 Incorrect 219 ms 5068 KB Output isn't correct
4 Correct 204 ms 5032 KB Output is correct
5 Incorrect 215 ms 1520 KB Output isn't correct
6 Incorrect 399 ms 6452 KB Output isn't correct
7 Incorrect 287 ms 1852 KB Output isn't correct
8 Incorrect 309 ms 9356 KB Output isn't correct
9 Incorrect 1791 ms 23732 KB Output isn't correct
10 Incorrect 735 ms 5096 KB Output isn't correct
11 Incorrect 1045 ms 6400 KB Output isn't correct
12 Incorrect 1683 ms 20200 KB Output isn't correct
13 Incorrect 1734 ms 23596 KB Output isn't correct