| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 531893 | mat50013 | Weirdtree (RMI21_weirdtree) | C++14 | 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.
#include "weirdtree.h"
#include <bits/stdc++.h>
using ll = long long;
const int NMAX(300005), INF(1000000005);
int v[NMAX], n;
struct node{
ll sum;
int max1, max2, fr1;
node operator+(node b){
node rez;
if(max1 < b.max1){
rez.max1 = b.max1, rez.fr1 = b.fr1;
rez.max2 = max1;
}
else if(max1 > b.max1){
rez.max1 = max1, rez.fr1 = fr1;
rez.max2 = b.max1;
}
else {
rez.max1 = max1;
rez.fr1 = fr1 + b.fr1;
rez.max2 = max(max2, b.max2);
}
rez.max2 = max(rez.max2, max(max2, b.max2));
rez.sum = sum + b.sum;
return rez;
}
}NUP={0, 0, -INF, 0};
struct SegTree{
vector<node> Arb;
inline void init(int n){
int put = 1;
while(put <= n)
put <<= 1;
put <<= 1;
Arb.resize(put);
}
inline void build(int nod, int st, int dr){
if(st == dr){
Arb[nod].max1 = Arb[nod].sum = v[st];
Arb[nod].max2 = -INF;
Arb[nod].fr1 = 1;
return;
}
int mij = (st + dr) / 2;
build(2 * nod, st, mij);
build(2 * nod + 1, mij + 1, dr);
Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
}
inline void UpdateNod(int nod, int unde){
Arb[nod].sum -= 1LL * (Arb[nod].max1 - unde) * Arb[nod].fr1;
Arb[nod].max1 = unde;
}
inline void push(int nod){
if(Arb[2 * nod].max1 > Arb[nod].max1)
UpdateNod(2 * nod, Arb[nod].max1);
if(Arb[2 * nod + 1].max1 > Arb[nod].max1)
UpdateNod(2 * nod + 1, Arb[nod].max1);
}
inline void Update(int nod, int st, int dr, int a, int b, int &extra, int capat){
if(Arb[nod].max1 <= capat - (extra > 0))
return;
if(a <= st && dr <= b && (extra == 0 || extra >= Arb[nod].fr1) && capat - (extra > 0) > Arb[nod].max2){
UpdateNod(nod, capat - (extra > 0));
if(extra > 0)
extra -= Arb[nod].fr1;
return;
}
push(nod);
int mij = (st + dr) / 2;
if(a <= mij)
Update(2 * nod, st, mij, a, b, extra, capat);
if(b > mij)
Update(2 * nod + 1, mij + 1, dr, a, b, extra, capat);
Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
}
inline node Unify(int nod, int st, int dr, int a, int b){
if(a <= st && dr <= b)
return Arb[nod];
int mij = (st + dr) / 2;
node rez1 = NUP, rez2 = NUP;
if(a <= mij)
rez1 = Unify(2 * nod, st, mij, a, b);
if(b > mij)
rez2 = Unify(2 * nod + 1, mij + 1, dr, a, b);
return rez1 + rez2;
}
inline void update2(int nod, int st, int dr, int poz, int val){
if(st == dr){
Arb[nod].max1 = Arb[nod].sum = val, Arb[nod].fr1 = 1;
Arb[nod].max2 = -INF;
return;
}
push(nod);
int mij = (st + dr) / 2;
if(poz <= mij)
update2(2 * nod, st, mij, poz, val);
else update2(2 * nod + 1, mij + 1, dr, poz, val);
Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
}
}Sol;
void initialise(int N, int Q, int h[]) {
n = N;
for(int i = 1; i <= N; ++i)
v[i] = h[i];
Sol.init(N);
Sol.build(1, 1, N);
}
void cut(int l, int r, int k) {
while(k > 0){
auto p = Sol.Unify(1, 1, n, l, r);
if(p.max1 == 0)
return;
ll nrP = 1LL * p.fr1 * (p.max1 - p.max2);
if(nrP <= k){
int val = 0;
Sol.Update(1, 1, n, l, r, val, p.max2);
k -= nrP;
}
else {
int val = k % p.fr1;
Sol.Update(1, 1, n, l, r, val, p.max1 - k / p.fr1);
k = 0;
}
}
}
void magic(int i, int x) {
Sol.update2(1, 1, n, i, x);
}
long long int inspect(int l, int r) {
auto p = Sol.Unify(1, 1, n, l, r);
return p.sum;
}