| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 590100 | davi_bart | Weirdtree (RMI21_weirdtree) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "weirdtree.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
struct segtree_beats {
struct node {
int ma1, ma2, freq;
ll sum;
int abbassa;
node(int a = -1, int b = -1, int c = 1, ll d = 0, int e = -1) {
ma1 = a;
ma2 = b;
freq = c;
sum = d;
abbassa = e;
}
};
static const int dim = 1 << 17;
vector<node> s = vector<node>(2 * dim);
void sist(int pos, int l, int r) {
if (s[pos].abbassa == -1) return;
if (s[pos].ma1 <= s[pos].abbassa) {
s[pos].abbassa = -1;
return;
}
s[pos].sum -= (ll)(s[pos].ma1 - s[pos].abbassa) * s[pos].freq;
s[pos].ma1 = s[pos].abbassa;
if (pos < dim) {
if (s[2 * pos].abbassa == -1 || s[2 * pos].abbassa > s[pos].abbassa) s[2 * pos].abbassa = s[pos].abbassa;
if (s[2 * pos + 1].abbassa == -1 || s[2 * pos + 1].abbassa > s[pos].abbassa) s[2 * pos + 1].abbassa = s[pos].abbassa;
}
s[pos].abbassa = -1;
}
void recalc(int pos) {
if (s[2 * pos].ma1 > s[2 * pos + 1].ma1) {
s[pos].ma1 = s[2 * pos].ma1;
s[pos].freq = s[2 * pos].freq;
s[pos].ma2 = max(s[2 * pos].ma2, s[2 * pos + 1].ma1);
} else if (s[2 * pos].ma1 < s[2 * pos + 1].ma1) {
s[pos].ma1 = s[2 * pos + 1].ma1;
s[pos].freq = s[2 * pos + 1].freq;
s[pos].ma2 = max(s[2 * pos].ma1, s[2 * pos + 1].ma2);
} else {
s[pos].ma1 = s[2 * pos].ma1;
s[pos].freq = s[2 * pos].freq + s[2 * pos + 1].freq;
s[pos].ma2 = max(s[2 * pos].ma2, s[2 * pos + 1].ma2);
}
s[pos].sum = s[2 * pos].sum + s[2 * pos + 1].sum;
}
void setta(int pos, int l, int r, int p, int val) {
sist(pos, l, r);
if (p < l || r < p) return;
if (l == r) {
s[pos] = {val, -1, 1, val, -1};
return;
}
int m = (l + r) / 2;
setta(2 * pos, l, m, p, val);
setta(2 * pos + 1, m + 1, r, p, val);
recalc(pos);
}
void setta(int p, int val) { setta(1, 0, dim - 1, p, val); }
int abbassa(int pos, int l, int r, int a, int b, int k, bool apply) {
sist(pos, l, r);
if (b < l || r < a) return 0;
if (s[pos].ma1 <= k) return 0;
if (a <= l && r <= b && s[pos].ma2 < k) {
ll tot = (ll)(s[pos].ma1 - k) * s[pos].freq;
if (apply) {
s[pos].abbassa = k;
sist(pos, l, r);
}
tot = min(tot, (int)2e9);
return tot;
}
int m = (l + r) / 2;
int tot = abbassa(2 * pos, l, m, a, b, k, apply) + abbassa(2 * pos + 1, m + 1, r, a, b, k, apply);
recalc(pos);
tot = min(tot, (int)2e9);
return tot;
}
int abbassa(int a, int b, int k, bool apply) { return abbassa(1, 0, dim - 1, a, b, k, apply); }
int abbassa1(int pos, int l, int r, int a, int b, int k, int count) {
sist(pos, l, r);
if (count == 0) return 0;
if (b < l || r < a) return 0;
if (s[pos].ma1 <= k) return 0;
if (a <= l && r <= b && s[pos].ma2 < k && (s[pos].ma1 - k) * s[pos].freq <= count) {
ll tot = (ll)(s[pos].ma1 - k) * s[pos].freq;
tot = min(tot, (int)2e9);
s[pos].abbassa = k;
sist(pos, l, r);
return tot;
}
int m = (l + r) / 2;
int tot = abbassa1(2 * pos, l, m, a, b, k, count);
count -= tot;
tot += abbassa1(2 * pos + 1, m + 1, r, a, b, k, count);
tot = min(tot, (int)2e9);
recalc(pos);
return tot;
}
int abbassa1(int a, int b, int k, int count) { return abbassa1(1, 0, dim - 1, a, b, k, count); }
ll query(int pos, int l, int r, int a, int b) {
sist(pos, l, r);
if (b < l || r < a) return 0;
if (a <= l && r <= b) return s[pos].sum;
int m = (l + r) / 2;
ll tot = query(2 * pos, l, m, a, b) + query(2 * pos + 1, m + 1, r, a, b);
return tot;
}
ll query(int a, int b) { return query(1, 0, dim - 1, a, b); }
} seg;
int N;
void dbg() {
// for (int i = 0; i < N; i++) cout << seg.query(i, i) << " ";
// cout << endl;
}
void initialise(signed n, signed Q, signed h[]) {
N = n;
for (int i = 0; i < N; i++) {
seg.setta(i, h[i + 1]);
}
dbg();
}
void cut(signed l, signed r, signed k) {
l--;
r--;
int x = 0, y = 1e9 + 10;
while (x < y) {
int m = (x + y + 1) / 2;
int q = seg.abbassa(l, r, m, 0);
if (q < k)
y = m - 1;
else
x = m;
}
k -= seg.abbassa(l, r, x + 1, 1);
// cout << x << " " << k << endl;
// dbg();
seg.abbassa1(l, r, x, k);
dbg();
}
void magic(signed i, signed x) {
i--;
seg.setta(i, x);
dbg();
}
ll inspect(signed l, signed r) {
l--;
r--;
return seg.query(l, r);
}