Submission #1091592

#TimeUsernameProblemLanguageResultExecution timeMemory
1091592tibinyteSafety (NOI18_safety)C++14
100 / 100
755 ms28752 KiB
#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 struct treap // implicit key treap { int prior, val, cnt; int maxi, lazy; treap *l = nullptr, *r = nullptr; treap(int val = 0) : val(val), lazy(0), prior(random(1, 1e9)), cnt(1), 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) { return 0; } if (t->l && 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:88:15: warning: 'treap::lazy' will be initialized after [-Wreorder]
   88 |     int maxi, lazy;
      |               ^~~~
safety.cpp:87:9: warning:   'long long int treap::prior' [-Wreorder]
   87 |     int prior, val, cnt;
      |         ^~~~~
safety.cpp:90:5: warning:   when initialized here [-Wreorder]
   90 |     treap(int val = 0) : val(val), lazy(0), prior(random(1, 1e9)), cnt(1), maxi(val) {}
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...