oj.uz

Submission #531896

# Submission time Handle Problem Language Result Execution time Memory
531896 2022-03-01T20:45:21 Z mat50013 Weirdtree (RMI21_weirdtree) C++14
100 / 100
 396 ms 37248 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 57 ms 9460 KB Output is correct
4 Correct 67 ms 9476 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 396 ms 37220 KB Output is correct
4 Correct 339 ms 37248 KB Output is correct
5 Correct 329 ms 37156 KB Output is correct
6 Correct 311 ms 37032 KB Output is correct
7 Correct 11 ms 7116 KB Output is correct
8 Correct 33 ms 7116 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7116 KB Output is correct
2 Correct 33 ms 7116 KB Output is correct
3 Correct 95 ms 28860 KB Output is correct
4 Correct 103 ms 28928 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 57 ms 9460 KB Output is correct
4 Correct 67 ms 9476 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 11 ms 7116 KB Output is correct
8 Correct 33 ms 7116 KB Output is correct
9 Correct 75 ms 9540 KB Output is correct
10 Correct 59 ms 9488 KB Output is correct
11 Correct 53 ms 9412 KB Output is correct
12 Correct 79 ms 9500 KB Output is correct
13 Correct 58 ms 9592 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 57 ms 9460 KB Output is correct
4 Correct 67 ms 9476 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 396 ms 37220 KB Output is correct
8 Correct 339 ms 37248 KB Output is correct
9 Correct 329 ms 37156 KB Output is correct
10 Correct 311 ms 37032 KB Output is correct
11 Correct 95 ms 28860 KB Output is correct
12 Correct 103 ms 28928 KB Output is correct
13 Correct 75 ms 9540 KB Output is correct
14 Correct 59 ms 9488 KB Output is correct
15 Correct 53 ms 9412 KB Output is correct
16 Correct 79 ms 9500 KB Output is correct
17 Correct 58 ms 9592 KB Output is correct
18 Correct 11 ms 7116 KB Output is correct
19 Correct 33 ms 7116 KB Output is correct
20 Correct 263 ms 36224 KB Output is correct
21 Correct 296 ms 36688 KB Output is correct
22 Correct 331 ms 36544 KB Output is correct
23 Correct 287 ms 36604 KB Output is correct
24 Correct 280 ms 36496 KB Output is correct