oj.uz

Submission #304564

# Submission time Handle Problem Language Result Execution time Memory
304564 2020-09-21T14:09:52 Z HynDuf Cake (CEOI14_cake) C++11
83.3333 / 100
 2000 ms 10028 KB 
#include <bits/stdc++.h>

#define task "C"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 250003;
int n, A, q, a[N];
set<ii> mxa;
int it[4 * N];
void build(int id, int l, int r)
{
    if (l == r)
    {
        it[id] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(id << 1, l, m);
    build((id << 1) | 1, m + 1, r);
    it[id] = max(it[id << 1], it[(id << 1) | 1]);
}
void update(int id, int l, int r, int p)
{
    if (l > p || r < p) return;
    if (l == r)
    {
        it[id] = a[p];
        return;
    }
    int m = (l + r) >> 1;
    update(id << 1, l, m, p);
    update((id << 1) | 1, m + 1, r, p);
    it[id] = max(it[id << 1], it[(id << 1) | 1]);
}
int query(int id, int l, int r, int L, int R)
{
    if (l > R || r < L || L > R) return -1e9;
    if (L <= l && r <= R) return it[id];
    int m = (l + r) >> 1;
    return max(query(id << 1, l, m, L, R), query((id << 1) | 1, m + 1, r, L, R));
}
int main()
{
#ifdef HynDuf
    freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    cin >> n >> A;
    rep(i, 1, n)
    {
        cin >> a[i];
        mxa.insert({a[i], i});
        if (SZ(mxa) > 11) mxa.erase(mxa.begin());
    }
    build(1, 1, n);
    cin >> q;
    while (q--)
    {
        char t;
        int x;
        cin >> t >> x;
        if (t == 'E')
        {
            int r;
            cin >> r;
            vii change;
            rep(i, 1, r - 1)
            {
                assert(!mxa.empty());
                auto it = mxa.end(); it--;
                if (it->S != x)
                {
                    change.pb({it->F + 1, it->S});
                    a[it->S]++;
                    update(1, 1, n, it->S);
                } else i--;
                mxa.erase(it);
            }
            auto it = mxa.lower_bound({a[x], 0});
            if (it != mxa.end() && it->F == a[x]) mxa.erase(it);
            if (change.empty())
            {
                if (mxa.empty()) a[x] = N;
                else a[x] = mxa.rbegin()->F + 1;
            } else a[x] = change.back().F - 1;
            change.pb({a[x], x});
            update(1, 1, n, x);

            for (ii v : change) mxa.insert(v);
            if (SZ(mxa) > 11) mxa.erase(mxa.begin());

        } else if (x > A)
        {
            int mx = query(1, 1, n, A + 1, x);
            int l = 1, r = A - 1;
            while (l <= r)
            {
                int m = (l + r) >> 1;
                if (query(1, 1, n, m, A - 1) > mx) l = m + 1;
                else r = m - 1;
            }
            cout << x - l << '\n';
        } else if (x < A)
        {
            int mx = query(1, 1, n, x, A - 1);
            int l = A + 1, r = n;
            while (l <= r)
            {
                int m = (l + r) >> 1;
                if (query(1, 1, n, A + 1, m) > mx) r = m - 1;
                else l = m + 1;
            }
            cout << r - x << '\n';
        } else cout << "0\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 31 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 632 KB Output is correct
2 Correct 375 ms 632 KB Output is correct
3 Correct 432 ms 512 KB Output is correct
4 Correct 231 ms 632 KB Output is correct
5 Correct 715 ms 640 KB Output is correct
6 Correct 586 ms 760 KB Output is correct
7 Correct 479 ms 640 KB Output is correct
8 Correct 251 ms 748 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 2424 KB Output is correct
2 Correct 411 ms 2296 KB Output is correct
3 Correct 423 ms 2296 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 514 ms 5624 KB Output is correct
6 Correct 707 ms 5664 KB Output is correct
7 Correct 607 ms 5624 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 508 KB Output is correct
2 Correct 96 ms 640 KB Output is correct
3 Correct 242 ms 1328 KB Output is correct
4 Correct 231 ms 1272 KB Output is correct
5 Correct 259 ms 760 KB Output is correct
6 Correct 482 ms 1656 KB Output is correct
7 Correct 323 ms 1016 KB Output is correct
8 Correct 242 ms 1816 KB Output is correct
9 Correct 1941 ms 9744 KB Output is correct
10 Correct 857 ms 1528 KB Output is correct
11 Correct 1248 ms 2108 KB Output is correct
12 Execution timed out 2021 ms 9332 KB Time limit exceeded
13 Execution timed out 2066 ms 10028 KB Time limit exceeded