oj.uz

답안 #304556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
304556 2020-09-21T13:53:24 Z HynDuf 케이크 (CEOI14_cake) C++14
0 / 100
 1215 ms 6396 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) > 9) 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)
            {
                if (mxa.empty()) break;
                auto it = mxa.end(); it--;
                change.pb({it->F + 1, it->S});
                a[it->S]++;
                update(1, 1, n, it->S);
                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) > 9) 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 664 ms 4984 KB Output isn't correct
2 Correct 390 ms 4908 KB Output is correct
3 Correct 448 ms 4912 KB Output is correct
4 Correct 238 ms 4984 KB Output is correct
5 Incorrect 723 ms 5364 KB Output isn't correct
6 Incorrect 594 ms 5896 KB Output isn't correct
7 Correct 475 ms 5752 KB Output is correct
8 Correct 251 ms 5752 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 558 ms 3832 KB Output is correct
2 Incorrect 371 ms 3576 KB Output isn't correct
3 Correct 405 ms 3576 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Runtime error 18 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 21 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 110 ms 888 KB Output isn't correct
2 Correct 97 ms 1016 KB Output is correct
3 Correct 227 ms 2296 KB Output is correct
4 Incorrect 227 ms 2296 KB Output isn't correct
5 Incorrect 251 ms 1912 KB Output isn't correct
6 Correct 452 ms 3320 KB Output is correct
7 Correct 332 ms 2788 KB Output is correct
8 Correct 240 ms 4472 KB Output is correct
9 Incorrect 103 ms 3448 KB Output isn't correct
10 Incorrect 835 ms 5160 KB Output isn't correct
11 Incorrect 1215 ms 6396 KB Output isn't correct
12 Incorrect 428 ms 3708 KB Output isn't correct
13 Runtime error 18 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)