Submission #1091222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091222		tibinyte	Safety (NOI18_safety)	C++17	100 / 100	776 ms	28752 KiB

safety

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random(int st, int dr)
{
    uniform_int_distribution<int> dist(st, dr);
    return dist(rng);
}

template <typename t>
using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint operator*(Mint oth)
    {
        return 1ll * val * oth.val;
    }
    void operator+=(Mint oth)
    {
        val = (*this + oth).val;
    }
    void operator-=(Mint oth)
    {
        val = (*this - oth).val;
    }
    void operator*=(Mint oth)
    {
        val = (*this * oth).val;
    }
};

Mint powmod(int a, int b)
{
    if (b == 0)
    {
        return 1;
    }
    if (b % 2 == 1)
    {
        return powmod(a, b - 1) * a;
    }
    Mint p = powmod(a, b / 2);
    return p * p;
}

/*
                 .___                 __                 __           .__
  ____  ____   __| _/____     _______/  |______ ________/  |_  ______ |  |__   ___________   ____
_/ ___\/  _ \ / __ |/ __ \   /  ___/\   __\__  \\_  __ \   __\/  ___/ |  |  \_/ __ \_  __ \_/ __ \
\  \__(  <_> ) /_/ \  ___/   \___ \  |  |  / __ \|  | \/|  |  \___ \  |   Y  \  ___/|  | \/\  ___/
 \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
     \/           \/    \/       \/            \/                 \/       \/     \/            \/
*/

#define int long long

const int inf = 1e9;

struct treap // implicit key treap
{
    int prior, val, cnt;
    int maxi, lazy;
    treap *l, *r;
    treap(int val) : val(val), lazy(0), prior(random(1, 1e9)), cnt(1), l(nullptr), r(nullptr), maxi(val) {}
};

int cnt(treap *t)
{
    return t ? t->cnt : 0;
}

void push(treap *&t)
{
    if (t && t->lazy)
    {
        t->maxi += t->lazy;
        t->val += t->lazy;
        if (t->l)
        {
            t->l->lazy += t->lazy;
        }
        if (t->r)
        {
            t->r->lazy += t->lazy;
        }
        t->lazy = 0;
    }
}

void pull(treap *&t)
{
    if (t)
    {
        assert(t->lazy == 0);
        push(t->l);
        push(t->r);
        t->cnt = cnt(t->l) + cnt(t->r) + 1;
        t->maxi = t->val;
        if (t->l)
        {
            t->maxi = max(t->maxi, t->l->maxi);
        }
        if (t->r)
        {
            t->maxi = max(t->maxi, t->r->maxi);
        }
    }
}

void merge(treap *&t, treap *l, treap *r)
{
    push(l), push(r);
    if (!l || !r)
    {
        t = (l ? l : r);
        return;
    }
    if (r->prior > l->prior)
    {
        merge(r->l, l, r->l);
        t = r;
    }
    else
    {
        merge(l->r, l->r, r);
        t = l;
    }
    pull(t);
}

void split(treap *t, treap *&l, treap *&r, int key, int add = 0)
{
    push(t);
    if (!t)
    {
        l = r = nullptr;
        return;
    }
    int curr_key = add + cnt(t->l) + 1;
    if (curr_key <= key)
    {
        split(t->r, t->r, r, key, add + cnt(t->l) + 1);
        l = t;
    }
    else
    {
        split(t->l, l, t->l, key, add);
        r = t;
    }
    pull(t);
}

int find_rank(treap *&t, int x)
{
    push(t);
    pull(t);
    if (!t || t->maxi < x)
    {
        return cnt(t);
    }
    if (t->l)
    {
        if (t->l->maxi > x)
        {
            return find_rank(t->l, x);
        }
    }
    if (t->val > x)
    {
        return cnt(t->l);
    }
    return cnt(t->l) + 1 + find_rank(t->r, x);
}

void insert(treap *&t, int x)
{
    treap *a, *b;
    a = b = nullptr;

    int my_rank = find_rank(t, x);

    split(t, a, b, my_rank);
    merge(a, a, new treap(x));
    merge(t, a, b);
}

void move(treap *&t, int pref, int h)
{
    treap *a, *b;
    a = b = nullptr;
    split(t, a, b, pref);
    if (b)
        b->lazy += h;
    if (a)
        a->lazy -= h;
    merge(t, a, b);
}

int pop(treap *&t)
{
    assert(cnt(t) >= 1);
    int ans = t->maxi;
    treap *lying = nullptr;
    split(t, t, lying, cnt(t) - 1);
    return ans;
}

struct line
{
    int a, b;
    line(int a = 0, int b = 0) : a(a), b(b) {}
    int eval(int x)
    {
        return a * x + b;
    }
    line operator+(line oth)
    {
        return line(a + oth.a, b + oth.b);
    }
};

struct slope_trick
{
    treap *t = nullptr;
    line rightmost;

    void shift(int dist)
    {
        move(t, cnt(t) - rightmost.a, dist);
        rightmost.b = rightmost.b - rightmost.a * dist;
    }

    void clean()
    {
        while (rightmost.a > 0)
        {
            int nxt = pop(t);
            rightmost = line(rightmost.a - 1, nxt + rightmost.b);
        }
    }

    void add(int x)
    {
        insert(t, x);
        insert(t, x);
        rightmost = rightmost + line(1, -x);
    }

    int getOpt()
    {
        clean();
        return rightmost.b;
    }
};

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, h;
    cin >> n >> h;
    vector<int> a(n + 1);
    slope_trick adam;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        adam.shift(h);
        adam.add(a[i]);
    }
    cout << adam.getOpt() << '\n';
}
/*
I cannot take this anymore
Saying everything I've said before
All these words, they make no sense
I find bliss in ignorance
Less I hear, the less you say
You'll find that out anyway
Just like before

Everything you say to me
(Takes me one step closer to the edge)
(And I'm about to break)
I need a little room to breathe
(Cause I'm one step closer to the edge)
(I'm about to break)
*/

Compilation message (stderr)

safety.cpp: In constructor 'treap::treap(long long int)':
safety.cpp:90:15: warning: 'treap::lazy' will be initialized after [-Wreorder]
   90 |     int maxi, lazy;
      |               ^~~~
safety.cpp:89:9: warning:   'long long int treap::prior' [-Wreorder]
   89 |     int prior, val, cnt;
      |         ^~~~~
safety.cpp:92:5: warning:   when initialized here [-Wreorder]
   92 |     treap(int val) : val(val), lazy(0), prior(random(1, 1e9)), cnt(1), l(nullptr), r(nullptr), maxi(val) {}
      |     ^~~~~
safety.cpp:91:16: warning: 'treap::r' will be initialized after [-Wreorder]
   91 |     treap *l, *r;
      |                ^
safety.cpp:90:9: warning:   'long long int treap::maxi' [-Wreorder]
   90 |     int maxi, lazy;
      |         ^~~~
safety.cpp:92:5: warning:   when initialized here [-Wreorder]
   92 |     treap(int val) : val(val), lazy(0), prior(random(1, 1e9)), cnt(1), l(nullptr), r(nullptr), maxi(val) {}
      |     ^~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29