oj.uz

Submission #304560

# Submission time Handle Problem Language Result Execution time Memory
304560 2020-09-21T14:05:24 Z HynDuf Cake (CEOI14_cake) C++11
73.3333 / 100
 1221 ms 2484 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 = 1e5 + 2;
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) 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) > 10) 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)
            {
                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->F == a[x]) mxa.erase(it);
            a[x] = (change.empty() ? (mxa.rbegin()->F + 1) : (change.back().F - 1));
            change.pb({a[x], x});
            update(1, 1, n, x);

            for (ii v : change) mxa.insert(v);
            if (SZ(mxa) > 10) 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 25 ms 640 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 552 KB Output is correct
2 Correct 390 ms 512 KB Output is correct
3 Correct 439 ms 632 KB Output is correct
4 Correct 228 ms 632 KB Output is correct
5 Correct 717 ms 760 KB Output is correct
6 Correct 588 ms 748 KB Output is correct
7 Correct 475 ms 640 KB Output is correct
8 Correct 249 ms 740 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 2484 KB Output is correct
2 Correct 395 ms 2248 KB Output is correct
3 Correct 400 ms 2240 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Runtime error 18 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 21 ms 1276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 20 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 572 KB Output is correct
2 Correct 100 ms 632 KB Output is correct
3 Correct 236 ms 1296 KB Output is correct
4 Correct 229 ms 1272 KB Output is correct
5 Correct 254 ms 888 KB Output is correct
6 Correct 462 ms 1656 KB Output is correct
7 Correct 322 ms 1016 KB Output is correct
8 Correct 234 ms 1792 KB Output is correct
9 Incorrect 97 ms 1784 KB Output isn't correct
10 Correct 843 ms 1656 KB Output is correct
11 Correct 1221 ms 2296 KB Output is correct
12 Incorrect 441 ms 2276 KB Output isn't correct
13 Runtime error 18 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)