oj.uz

답안 #304641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
304641 2020-09-21T16:18:23 Z HynDuf 케이크 (CEOI14_cake) C++11
100 / 100
 464 ms 5112 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 = 250002;
int read(){int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0',ch=getchar();}return s*f;}
char readch() {char c; do c = getchar(); while (c == '\n' || c == ' '); return c;}
template <typename T> inline void wrip(T x) {if (x > 9) wrip(x / 10); putchar(x%10 + 48); }
template <typename T> inline void writeln(T x) {if (x < 0) putchar('-'), x = -x; wrip(x); putchar('\n');}
int n, A, q, a[N], save[N], newE[N], bit[2][N];
set<ii> mxa;
void upd(int p, int v, int id)
{
    for (; p < n; p += p & (-p)) bit[id][p] = max(bit[id][p], v);
}
void update(int p, int v)
{
    if (p > A) upd(p - A, v, 1);
    else if (p < A) upd(A - p, v, 0);
}
int query(int id, int p)
{
    int res = 0;
    for (; p; p -= p & (-p)) res = max(res, bit[id][p]);
    return res;
}
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;
    n = read(), A = read();
    rep(i, 1, n)
    {
        a[i] = read();
        update(i, a[i]);
        mxa.insert({a[i], i});
        if (SZ(mxa) > 10) mxa.erase(mxa.begin());
    }
    int numE = 1;
    q = read();
    while (q--)
    {
        char t;
        int x;
        t = readch();
        x = read();
        if (t == 'E')
        {
            numE++;
            int r;
            r = read();
            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(it->S, it->F + 1);
                } else i--;
                mxa.erase(it);
            }
            auto it = mxa.lower_bound({a[x], 0});
            if (it != mxa.end() && 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(x, a[x]);

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

        } else if (x > A)
        {
            int mx = query(1, x - A);
            int l = 1, r = A - 1;
            while (l <= r)
            {
                int m = (l + r) >> 1;
                int cur = (newE[m] == numE) ? save[m] : query(0, A - m);
                //newE[m] = numE;
                save[m] = cur;
                if (cur > mx) l = m + 1;
                else r = m - 1;
            }
            writeln(x - l);
        } else if (x < A)
        {
            int mx = query(0, A - x);
            int l = A + 1, r = n;
            while (l <= r)
            {
                int m = (l + r) >> 1;
                int cur = (newE[m] == numE) ? save[m] : query(1, m - A);
                //newE[m] = numE;
                save[m] = cur;
                if (cur > mx) r = m - 1;
                else l = m + 1;
            }
            writeln(r - x);
        } else puts("0");
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 4 ms 384 KB Output is correct
5 Correct 11 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 339 ms 512 KB Output is correct
2 Correct 187 ms 512 KB Output is correct
3 Correct 231 ms 544 KB Output is correct
4 Correct 123 ms 512 KB Output is correct
5 Correct 362 ms 892 KB Output is correct
6 Correct 305 ms 640 KB Output is correct
7 Correct 242 ms 640 KB Output is correct
8 Correct 132 ms 640 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 2040 KB Output is correct
2 Correct 50 ms 1824 KB Output is correct
3 Correct 49 ms 1672 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 86 ms 3196 KB Output is correct
6 Correct 86 ms 3320 KB Output is correct
7 Correct 81 ms 2808 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 512 KB Output is correct
2 Correct 21 ms 512 KB Output is correct
3 Correct 46 ms 1152 KB Output is correct
4 Correct 64 ms 1244 KB Output is correct
5 Correct 94 ms 760 KB Output is correct
6 Correct 82 ms 1660 KB Output is correct
7 Correct 80 ms 1016 KB Output is correct
8 Correct 117 ms 1400 KB Output is correct
9 Correct 463 ms 5112 KB Output is correct
10 Correct 311 ms 1528 KB Output is correct
11 Correct 360 ms 2168 KB Output is correct
12 Correct 464 ms 4216 KB Output is correct
13 Correct 403 ms 4856 KB Output is correct