oj.uz

Submission #304559

# Submission time Handle Problem Language Result Execution time Memory
304559 2020-09-21T14:03:14 Z HynDuf Cake (CEOI14_cake) C++11
0 / 100
 1202 ms 2424 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);
            }
            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
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 652 ms 560 KB Output isn't correct
2 Correct 391 ms 632 KB Output is correct
3 Correct 435 ms 556 KB Output is correct
4 Correct 234 ms 636 KB Output is correct
5 Incorrect 708 ms 760 KB Output isn't correct
6 Incorrect 600 ms 764 KB Output isn't correct
7 Correct 470 ms 760 KB Output is correct
8 Correct 245 ms 640 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 2416 KB Output is correct
2 Incorrect 367 ms 2296 KB Output isn't correct
3 Correct 401 ms 2424 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Runtime error 18 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 19 ms 1272 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 504 KB Output isn't correct
2 Correct 93 ms 512 KB Output is correct
3 Correct 228 ms 1272 KB Output is correct
4 Incorrect 225 ms 1272 KB Output isn't correct
5 Incorrect 250 ms 888 KB Output isn't correct
6 Correct 459 ms 1532 KB Output is correct
7 Correct 316 ms 1016 KB Output is correct
8 Correct 235 ms 1912 KB Output is correct
9 Incorrect 105 ms 1784 KB Output isn't correct
10 Incorrect 821 ms 1528 KB Output isn't correct
11 Incorrect 1202 ms 2168 KB Output isn't correct
12 Incorrect 423 ms 2316 KB Output isn't correct
13 Runtime error 18 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)