Submission #413626

#	Time	Username	Problem	Language	Result	Execution time	Memory
413626		iANikzad	Cake (CEOI14_cake)	C++14	100 / 100	1025 ms	11428 KiB

cake

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 2.5e5 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 20;
const int SQ = 400;

int n, a;

int d[maxn];
vector<int> tp;

int seg[2][maxn * 4];

bool cmp(int x,int y) {return d[x] > d[y]; }

void UPDATE(int *seg, int pos,int val,int s,int e,int id)
{
    if(s == e)
    {
        seg[id] = val;
        return;
    }

    int mid = (s + e) / 2;

    if(pos > mid) UPDATE(seg, pos, val, mid + 1, e, id*2 + 1);
    else UPDATE(seg, pos, val, s, mid, id*2 + 0);

    seg[id] = max(seg[id*2 + 0], seg[id*2 + 1]);
}

int MAX(int *seg,int l,int r,int s,int e,int id)
{
    if(l > e || r < s)
        return 0;

    if(l <= s && r >= e)
        return seg[id];

    int mid = (s + e) / 2;

    return max(MAX(seg, l, r, s, mid, id*2 + 0), MAX(seg, l, r, mid + 1, e, id*2 + 1));
}

int GET(int *seg,int val,int s,int e,int id)
{
    if(val > seg[id]) return e;
    if(s == e) return s - (seg[id] > val);

    int mid = (s + e) / 2;

    if(seg[id*2 + 0] >= val) return GET(seg, val, s, mid, id*2 + 0);
    return GET(seg, val, mid + 1, e, id*2 + 1);
}

void Enhance(int i,int e)
{
    auto it = find(all(tp), i);
    if(it != tp.end()) tp.erase(it);

    for(int i = 0;i < e - 1; i++)
    {
        d[tp[i]]++;
        if(tp[i] > a) UPDATE(seg[0], tp[i] - a, d[tp[i]], 1, n - a, 1);
        else if(tp[i] < a) UPDATE(seg[1], a - tp[i], d[tp[i]], 1, a - 1, 1);
    }

    d[i] = d[tp[e - 1]] + 1;
    if(i > a) UPDATE(seg[0], i - a, d[i], 1, n - a, 1);
    else if(i < a) UPDATE(seg[1], a - i, d[i], 1, a - 1, 1);

    tp.insert(tp.begin() + e - 1, i);
    if(tp.size() > 10) tp.pop_back();
}

int Find(int b)
{
    if(b == a) return 0;
    if(b > a) return GET(seg[1], MAX(seg[0], 1, b - a, 1, n - a, 1), 1, a - 1, 1) + b - a;
    return GET(seg[0], MAX(seg[1], 1, a - b, 1, a - 1, 1), 1, n - a, 1) + a - b;
}

int32_t main()
{
    FAST;

    cin >> n >> a;

    for(int i = 1; i <= n; i++) cin >> d[i], tp.pb(d[i]);

    sort(all(tp), cmp);
    while(tp.size() > 10) tp.pop_back();

    for(int i = a + 1; i <= n; i++) UPDATE(seg[0], i - a, d[i], 1, n - a, 1);
    for(int i = a - 1; i >= 1; i--) UPDATE(seg[1], a - i, d[i], 1, a - 1, 1);

    int q; cin >> q;
    while(q--)
    {
        char type; cin >> type;

        if(type == 'E')
        {
            int i, e;
            cin >> i >> e;

            Enhance(i, e);
        }

        if(type == 'F')
        {
            int b;
            cin >> b;

            cout << Find(b) << "\n";
        }
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50