| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 561215 |
2022-05-12T13:17:57 Z |
blue |
Weirdtree (RMI21_weirdtree) |
C++17 |
|
2000 ms |
51552 KB |
#include "weirdtree.h"
#include <vector>
#include <iostream>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
const int mx = 300'000;
const ll INF = 1'000'000'000'000'000'000LL;
struct info
{
int l;
int r;
ll mxv;
int mxct;
ll mxv2;
ll sm;
info()
{
;
}
info(int i, ll v)
{
l = r = i;
mxv = v;
mxct = 1;
mxv2 = -1;
sm = v;
}
};
void combine(info& res, const info& a, const info& b)
{
// res.l = a.l;
// res.r = b.r; //if slow, get rid of this part
res.mxv = max(a.mxv, b.mxv);
res.mxct = (a.mxv == res.mxv ? a.mxct : 0) + (b.mxv == res.mxv ? b.mxct : 0);
res.mxv2 = -INF;
for(ll z : {a.mxv, b.mxv, a.mxv2, b.mxv2})
if(z < res.mxv)
res.mxv2 = max(res.mxv2, z);
res.sm = a.sm + b.sm;
}
info get_combine(const info& a, const info& b)
{
info res;
combine(res, a, b);
res.l = a.l;
res.r = b.r;
return res;
}
int N, Q;
vi h;
struct segtree
{
vector<info> v = vector<info>(mx<<2);
void build(int i, int l, int r)
{
if(l == r)
v[i] = info(l, h[l]);
else
{
build(2*i, l, (l+r)/2);
build(2*i+1, (l+r)/2+1, r);
combine(v[i], v[2*i], v[2*i+1]);
v[i].l = l;
v[i].r = r;
}
}
void maxlim(int i, int L, int R, ll z)
{
if(v[i].mxv <= z) return;
if(R < v[i].l || v[i].r < L) return;
else if(L <= v[i].l && v[i].r <= R)
{
if(v[i].mxv2 < z && z < v[i].mxv)
{
v[i].sm += (z - v[i].mxv) * v[i].mxct;
v[i].mxv = z;
}
else
{
if(v[i].l != v[i].r)
{
maxlim(2*i, 0, N-1, v[i].mxv);
maxlim(2*i+1, 0, N-1, v[i].mxv);
maxlim(2*i, L, R, z);
maxlim(2*i+1, L, R, z);
combine(v[i], v[2*i], v[2*i+1]);
}
}
}
else
{
maxlim(2*i, 0, N-1, v[i].mxv);
maxlim(2*i+1, 0, N-1, v[i].mxv);
maxlim(2*i, L, R, z);
maxlim(2*i+1, L, R, z);
combine(v[i], v[2*i], v[2*i+1]);
}
// cerr << "maxlim : " << v[i].l << ' ' << v[i].r << " -> op = " << L << ' ' << R << ' ' << z << '\n';
// cerr << v[i].mxv << ' ' << v[i].mxct << " " << v[i].mxv2 << '\n';
}
ll rangesum(int i, int L, int R)
{
if(R < v[i].l || v[i].r < L) return 0;
else if(L <= v[i].l && v[i].r <= R)
{
return v[i].sm;
}
else
{
maxlim(2*i, 0, N-1, v[i].mxv);
maxlim(2*i+1, 0, N-1, v[i].mxv);
return rangesum(2*i, L, R) + rangesum(2*i+1, L, R);
}
}
void magic(int i, int p, ll x)
{
if(v[i].l == v[i].r)
{
v[i] = info(p, x);
}
else
{
maxlim(2*i, 0, N-1, v[i].mxv);
maxlim(2*i+1, 0, N-1, v[i].mxv);
if(p <= (v[i].l + v[i].r) / 2)
{
magic(2*i, p, x);
}
else
{
magic(2*i+1, p, x);
}
combine(v[i], v[2*i], v[2*i+1]);
}
}
ll rangemax(int i, int L, int R)
{
if(R < v[i].l || v[i].r < L)
return -INF;
else if(L <= v[i].l && v[i].r <= R)
return v[i].mxv;
else
{
maxlim(2*i, 0, N-1, v[i].mxv);
maxlim(2*i+1, 0, N-1, v[i].mxv);
return max(rangemax(2*i, L, R), rangemax(2*i+1, L, R));
}
}
info scombine(int i, int L, int R)
{
if(L <= v[i].l && v[i].r <= R)
return v[i];
maxlim(2*i, 0, N-1, v[i].mxv);
maxlim(2*i+1, 0, N-1, v[i].mxv);
if(R <= (v[i].l + v[i].r)/2)
return scombine(2*i, L, R);
else if(L >= (v[i].l + v[i].r)/2 + 1)
return scombine(2*i+1, L, R);
else
return get_combine(scombine(2*i, L, R), scombine(2*i+1, L, R));
}
ll dec(int i, int L, int R, ll c)
{
if(R < v[i].l || v[i].r < L)
return 0;
if(v[i].mxv <= 0)
return 0;
if(c <= 0)
return 0;
else if(L <= v[i].l && v[i].r <= R)
{
// cerr << "case 1\n";
if(v[i].mxct <= c)
{
// cerr << "case 1A\n";
ll res = v[i].mxct;
maxlim(i, L, R, v[i].mxv - 1);
// cerr << "dec " << v[i].l << ' ' << v[i].r << " " << ' ' << L << ' ' << R << ' ' << c << '\n';
return res;
}
else
{
// cerr << "case 1B\n";
maxlim(2*i, 0, N-1, v[i].mxv);
maxlim(2*i+1, 0, N-1, v[i].mxv);
ll l_used, r_used;
if(v[2*i].mxv == v[i].mxv)
l_used = dec(2*i, L, R, c);
else
l_used = 0;
c -= l_used;
// cerr << "l_used = " << l_used << '\n';
if(v[2*i + 1].mxv == v[i].mxv)
r_used = dec(2*i+1, L, R, c);
else
r_used = 0;
combine(v[i], v[2*i], v[2*i+1]);
// cerr << "dec " << v[i].l << ' ' << v[i].r << " " << ' ' << L << ' ' << R << ' ' << c << '\n';
return l_used + r_used;
}
}
else
{
maxlim(2*i, 0, N-1, v[i].mxv);
maxlim(2*i+1, 0, N-1, v[i].mxv);
ll l_used = dec(2*i, L, R, c);
c -= l_used;
ll r_used = dec(2*i+1, L, R, c);
combine(v[i], v[2*i], v[2*i+1]);
// cerr << "dec " << v[i].l << ' ' << v[i].r << " " << ' ' << L << ' ' << R << ' ' << c << '\n';
return l_used + r_used;
}
}
};
segtree S;
void initialise(int N_, int Q_, int h_[]) {
N = N_;
Q = Q_;
h = vi(N);
for(int i = 0; i < N; i++)
h[i] = h_[i+1];
S.build(1, 0, N-1);
// for(int i = 0; i < N; i++) cerr << S.rangemax(1, i, i) << ' ';
// cerr << '\n';
}
void cut(int l, int r, int k)
{
l--;
r--;
ll prevk = -1;
while(k >= 0)
{
// cerr << "k = " << k << '\n';
info z = S.scombine(1, l, r);
if(z.mxv <= 0) break;
z.mxv2 = max(z.mxv2, 0LL);
ll req = (z.mxv - z.mxv2) * z.mxct;
// cerr << "mxv = " << z.mxv << '\n';
// cerr << "req = " << req << '\n';
if(req <= k)
{
S.maxlim(1, l, r, z.mxv2);
k -= req;
}
else
{
ll fullturns = k / z.mxct;
// cerr << "fullturns = " << fullturns << '\n';
if(fullturns >= 1)
{
// cerr << "maxlim " << l << ' ' << r << ' ' << z.mxv - fullturns << '\n';
S.maxlim(1, l, r, z.mxv - fullturns);
}
k -= fullturns * z.mxct;
// cerr << "k = " << k << '\n';
if(k >= 1)
S.dec(1, l, r, k);
break;
}
if(k == prevk)
break;
prevk = k;
}
// cerr << "! ";
// for(int i = 0; i < N; i++) cerr << S.rangemax(1, i, i) << ' ';
// cerr << '\n';
}
void magic(int i, int x)
{
i--;
S.magic(1, i, x);
cerr << "! ";
for(int i = 0; i < N; i++) cerr << S.rangemax(1, i, i) << ' ';
cerr << '\n';
}
long long int inspect(int l, int r) {
l--;
r--;
return S.rangesum(1, l, r);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
814 ms |
3660 KB |
Output is correct |
| 2 |
Correct |
788 ms |
3544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
814 ms |
3660 KB |
Output is correct |
| 2 |
Correct |
788 ms |
3544 KB |
Output is correct |
| 3 |
Execution timed out |
2057 ms |
19824 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2007 ms |
51552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
814 ms |
3660 KB |
Output is correct |
| 2 |
Correct |
788 ms |
3544 KB |
Output is correct |
| 3 |
Execution timed out |
2057 ms |
19824 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
814 ms |
3660 KB |
Output is correct |
| 2 |
Correct |
788 ms |
3544 KB |
Output is correct |
| 3 |
Execution timed out |
2057 ms |
19824 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
