oj.uz

Submission #304558

# Submission time Handle Problem Language Result Execution time Memory
304558 2020-09-21T14:02:34 Z HynDuf Cake (CEOI14_cake) C++11
0 / 100
 446 ms 3328 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);
                    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 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 240 ms 632 KB Output is correct
5 Runtime error 7 ms 1172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 6 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 6 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 252 ms 888 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 22 ms 3328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 22 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 18 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 19 ms 1280 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
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 2 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 10 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 11 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 13 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 20 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 98 ms 1784 KB Output isn't correct
10 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 7 ms 1184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 446 ms 2296 KB Output isn't correct
13 Runtime error 19 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)