이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
struct DATA
{
int mx1 = -inf, mx2 = -inf, cnt = 0, s = 0;
void print()
{
cout << mx1 << ' ' << mx2 << ' ' << cnt << ' ' << s << endl;
}
};
const int MXN = 3e5 + 5;
int n;
int arr[MXN];
DATA st[MXN << 2];
DATA combine(DATA x, DATA y)
{
if (x.mx1 == y.mx1) return {x.mx1, max(x.mx2, y.mx2), x.cnt + y.cnt, x.s + y.s};
else if (x.mx1 > y.mx1) return {x.mx1, max(x.mx2, y.mx1), x.cnt, x.s + y.s};
else return {y.mx1, max(x.mx1, y.mx2), y.cnt, x.s + y.s};
}
void build(int l, int r, int x)
{
if (l == r)
{
st[x] = {arr[l], -inf, 1, arr[l]};
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x);
build(mid + 1, r, 2*x + 1);
st[x] = combine(st[2*x], st[2*x + 1]);
}
void relax(int x, int val)
{
if (st[x].mx1 > val)
{
st[x].s -= (st[x].mx1 - val) * st[x].cnt;
st[x].mx1 = val;
}
}
void upd(int l, int r, int x, int lx, int rx, int val)
{
if (lx > rx) return;
relax(x, st[x / 2].mx1);
if (l > rx || r < lx) return;
if (st[x].mx1 <= val) return;
if (!(l >= lx && r <= rx) || st[x].mx2 >= val)
{
int mid = (l + r) >> 1;
upd(l, mid, 2*x, lx, rx, val);
upd(mid + 1, r, 2*x + 1, lx, rx, val);
st[x] = combine(st[2*x], st[2*x + 1]);
}
else relax(x, val);
}
void make(int l, int r, int x, int ind)
{
relax(x, st[x / 2].mx1);
if (!(l <= ind && ind <= r)) return;
if (l == r)
{
st[x] = {arr[l], -inf, 1, arr[l]};
return;
}
int mid = (l + r) >> 1;
make(l, mid, 2*x, ind);
make(mid + 1, r, 2*x + 1, ind);
st[x] = combine(st[2*x], st[2*x + 1]);
}
int gets(int l, int r, int x, int lx, int rx)
{
if (lx > rx) return 0;
relax(x, st[x / 2].mx1);
if (l > rx || r < lx) return 0;
if (l >= lx && r <= rx) return st[x].s;
int mid = (l + r) >> 1;
return gets(l, mid, 2*x, lx, rx) + gets(mid + 1, r, 2*x + 1, lx, rx);
}
DATA get(int l, int r, int x, int lx, int rx)
{
if (lx > rx) return {-inf, -inf, 0, 0};
relax(x, st[x / 2].mx1);
if (l > rx || r < lx) return {-inf, -inf, 0, 0};
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}
array<int, 2> findkthval(int l, int r, int x, int lx, int rx, int k, int val)
{
if (lx > rx) return {-1, 0};
if (l > rx || r < lx) return {-1, 0};
relax(x, st[x / 2].mx1);
if (l >= lx && r <= rx && (st[x].mx1 != val || st[x].cnt < k)) return {-1, (st[x].mx1 == val) * st[x].cnt};
if (l == r) return {l, (st[x].mx1 == val) * st[x].cnt};
int mid = (l + r) >> 1;
array<int, 2> A = findkthval(l, mid, 2*x, lx, rx, k, val);
if (A[0] != -1) return A;
return findkthval(mid + 1, r, 2*x + 1, lx, rx, k - A[1], val);
}
void initialise(int N, int Q, int h[])
{
for (int i = 1; i <= N; i++) arr[i] = h[i];
n = N;
st[0] = {inf, inf, 0, 0};
build(1, n, 1);
}
void cut(int l, int r, int k)
{
while (1)
{
DATA x = get(1, n, 1, l, r);
if (x.mx1 == 0) break;
int lw = max(0, x.mx2);
if (x.mx1 - (k / x.cnt) > lw) break;
upd(1, n, 1, l, r, lw);
k -= (x.mx1 - lw) * x.cnt;
}
if (!k) return;
DATA x = get(1, n, 1, l, r);
if (x.mx1 == 0) return;
array<int, 2> q = findkthval(1, n, 1, l, r, (k - 1) % x.cnt + 1, x.mx1);
assert(l <= q[0] && q[0] <= r);
upd(1, n, 1, l, q[0], x.mx1 - ((k + x.cnt - 1) / x.cnt));
upd(1, n, 1, q[0] + 1, r, x.mx1 - (k / x.cnt));
}
void magic(int i, int x)
{
arr[i] = x;
make(1, n, 1, i);
}
long long int inspect(int l, int r)
{
return gets(1, n, 1, l, r);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |