oj.uz

Submission #697675

# Submission time Handle Problem Language Result Execution time Memory
697675 2023-02-10T17:25:16 Z tamthegod Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 30232 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);
            while(S.size() > 10) S.erase(--S.end());
        }
        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 Execution timed out 2080 ms 1548 KB Time limit exceeded
2 Incorrect 315 ms 5632 KB Output isn't correct
3 Incorrect 365 ms 5636 KB Output isn't correct
4 Incorrect 246 ms 5628 KB Output isn't correct
5 Execution timed out 2081 ms 6024 KB Time limit exceeded
6 Incorrect 471 ms 7588 KB Output isn't correct
7 Incorrect 398 ms 7684 KB Output isn't correct
8 Incorrect 256 ms 7584 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 429 ms 11276 KB Output isn't correct
2 Incorrect 274 ms 11384 KB Output isn't correct
3 Incorrect 281 ms 11184 KB Output isn't correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 496 ms 25068 KB Output isn't correct
6 Incorrect 607 ms 25104 KB Output isn't correct
7 Incorrect 445 ms 25080 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 1100 KB Output isn't correct
2 Incorrect 71 ms 1356 KB Output isn't correct
3 Incorrect 181 ms 5968 KB Output isn't correct
4 Incorrect 167 ms 6028 KB Output isn't correct
5 Execution timed out 2079 ms 1024 KB Time limit exceeded
6 Incorrect 345 ms 8080 KB Output isn't correct
7 Incorrect 243 ms 3360 KB Output isn't correct
8 Incorrect 233 ms 11892 KB Output isn't correct
9 Incorrect 1374 ms 30232 KB Output isn't correct
10 Execution timed out 2074 ms 904 KB Time limit exceeded
11 Execution timed out 2076 ms 4388 KB Time limit exceeded
12 Incorrect 1313 ms 26276 KB Output isn't correct
13 Incorrect 1583 ms 30112 KB Output isn't correct