oj.uz

Submission #413626

# Submission time Handle Problem Language Result Execution time Memory
413626 2021-05-29T06:37:19 Z iANikzad Cake (CEOI14_cake) C++14
100 / 100
 1025 ms 11428 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 8 ms 332 KB Output is correct
5 Correct 19 ms 632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 556 KB Output is correct
2 Correct 169 ms 596 KB Output is correct
3 Correct 222 ms 612 KB Output is correct
4 Correct 163 ms 600 KB Output is correct
5 Correct 336 ms 908 KB Output is correct
6 Correct 249 ms 900 KB Output is correct
7 Correct 251 ms 920 KB Output is correct
8 Correct 180 ms 844 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 3184 KB Output is correct
2 Correct 246 ms 2880 KB Output is correct
3 Correct 239 ms 2660 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 336 ms 5604 KB Output is correct
6 Correct 319 ms 5564 KB Output is correct
7 Correct 297 ms 5356 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 476 KB Output is correct
2 Correct 66 ms 496 KB Output is correct
3 Correct 125 ms 1540 KB Output is correct
4 Correct 147 ms 1480 KB Output is correct
5 Correct 208 ms 648 KB Output is correct
6 Correct 235 ms 2532 KB Output is correct
7 Correct 270 ms 1080 KB Output is correct
8 Correct 155 ms 2284 KB Output is correct
9 Correct 1022 ms 10388 KB Output is correct
10 Correct 717 ms 1416 KB Output is correct
11 Correct 794 ms 4048 KB Output is correct
12 Correct 1025 ms 9764 KB Output is correct
13 Correct 911 ms 11428 KB Output is correct