Submission #531896

#	Time	Username	Problem	Language	Result	Execution time	Memory
531896		mat50013	Weirdtree (RMI21_weirdtree)	C++14	100 / 100	396 ms	37248 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
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];
        push(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;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29