oj.uz

Submission #754785

# Submission time Handle Problem Language Result Execution time Memory
754785 2023-06-08T14:12:32 Z maomao90 Weirdtree (RMI21_weirdtree) C++17
100 / 100
 472 ms 37328 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if(0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 300005;

int n;
int h[MAXN];

ll sm[MAXN * 4];
int mx[MAXN * 4], mxc[MAXN * 4], smx[MAXN * 4], lz[MAXN * 4];
#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
void propo(int u, int lo, int hi) {
    if (lz[u] == 0) {
        return;
    }
    MLR;
    if (mx[u] + lz[u] == mx[lc]) {
        mx[lc] -= lz[u];
        sm[lc] -= (ll) lz[u] * mxc[lc];
        lz[lc] += lz[u];
    }
    if (mx[u] + lz[u] == mx[rc]) {
        mx[rc] -= lz[u];
        sm[rc] -= (ll) lz[u] * mxc[rc];
        lz[rc] += lz[u];
    }
    lz[u] = 0;
}
void merge(int u, int lo, int hi) {
    MLR;
    if (mx[lc] == mx[rc]) {
        mx[u] = mx[lc];
        mxc[u] = mxc[lc] + mxc[rc];
        smx[u] = max(smx[lc], smx[rc]);
    } else if (mx[lc] > mx[rc]) {
        mx[u] = mx[lc];
        mxc[u] = mxc[lc];
        smx[u] = max(smx[lc], mx[rc]);
    } else {
        mx[u] = mx[rc];
        mxc[u] = mxc[rc];
        smx[u] = max(smx[rc], mx[lc]);
    }
    sm[u] = sm[lc] + sm[rc];
}
void init(int u = 1, int lo = 1, int hi = n) {
    lz[u] = 0;
    if (lo == hi) {
        sm[u] = h[lo];
        mx[u] = h[lo];
        mxc[u] = 1;
        smx[u] = -1;
        return;
    }
    MLR;
    init(lc, lo, mid);
    init(rc, mid + 1, hi);
    merge(u, lo, hi);
}
void upd(int p, int x, int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        sm[u] = x;
        mx[u] = x;
        mxc[u] = 1;
        smx[u] = -1;
        return;
    }
    MLR;
    propo(u, lo, hi);
    if (p <= mid) {
        upd(p, x, lc, lo, mid);
    } else {
        upd(p, x, rc, mid + 1, hi);
    }
    merge(u, lo, hi);
}
void updmn(int s, int e, int x, int u = 1, int lo = 1, int hi = n) {
    if (mx[u] <= x) {
        return;
    }
    if (lo >= s && hi <= e && smx[u] < x) {
        lz[u] += mx[u] - x;
        sm[u] -= (ll) (mx[u] - x) * mxc[u];
        mx[u] = x;
        return;
    }
    MLR;
    propo(u, lo, hi);
    if (s <= mid) {
        updmn(s, e, x, lc, lo, mid);
    }
    if (e > mid) {
        updmn(s, e, x, rc, mid + 1, hi);
    }
    merge(u, lo, hi);
}
iii qmx(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        return {mx[u], mxc[u], smx[u]};
    }
    MLR;
    propo(u, lo, hi);
    if (e <= mid) {
        return qmx(s, e, lc, lo, mid);
    } else if (s > mid) {
        return qmx(s, e, rc, mid + 1, hi);
    } else {
        auto [lmx, lmxc, lsmx] = qmx(s, e, lc, lo, mid);
        auto [rmx, rmxc, rsmx] = qmx(s, e, rc, mid + 1, hi);
        int mx, mxc, smx;
        if (lmx == rmx) {
            mx = lmx;
            mxc = lmxc + rmxc;
            smx = max(lsmx, rsmx);
        } else if (lmx > rmx) {
            mx = lmx;
            mxc = lmxc;
            smx = max(lsmx, rmx);
        } else {
            mx = rmx;
            mxc = rmxc;
            smx = max(rsmx, lmx);
        }
        return {mx, mxc, smx};
    }
}
ll qsm(int s, int e, int u = 1, int lo = 1, int hi = n) {
    cerr << "  " << lo << ' ' << hi << ": " << sm[u] << '\n';
    if (lo >= s && hi <= e) {
        return sm[u];
    }
    MLR;
    propo(u, lo, hi);
    ll res = 0;
    if (s <= mid) {
        res += qsm(s, e, lc, lo, mid);
    }
    if (e > mid) {
        res += qsm(s, e, rc, mid + 1, hi);
    }
    return res;
}
int lb(int s, int x, int &c, int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        c -= mx[u] == x;
        return lo;
    }
    MLR;
    propo(u, lo, hi);
    if (mid < s) {
        return lb(s, x, c, rc, mid + 1, hi);
    } else if (lo < s || mx[lc] > x) {
        int res = lb(s, x, c, lc, lo, mid);
        if (c < 0) {
            return res;
        }
        return lb(s, x, c, rc, mid + 1, hi);
    } else {
        if (mx[lc] < x) {
            return lb(s, x, c, rc, mid + 1, hi);
        }
        if (mxc[lc] <= c) {
            c -= mxc[lc];
            return lb(s, x, c, rc, mid + 1, hi);
        } else {
            return lb(s, x, c, lc, lo, mid);
        }
    }
}

void initialise(int N, int Q, int H[]) {
    n = N;
    REP (i, 1, n + 1) {
        h[i] = H[i];
    }
    init();
}
void cut(int l, int r, int k) {
    cerr << "CUT " << l << ' ' << r << ' ' << k << '\n';
    while (k) {
        auto [mx, mxc, smx] = qmx(l, r);
        cerr << mx << ' ' << smx << ' ' << mxc << '\n';
        if (mx == 0) {
            break;
        }
        mxto(smx, 0);
        if ((ll) (mx - smx) * mxc <= k) {
            k -= (ll) (mx - smx) * mxc;
            cerr << " UPDMN: " << l << ' ' << r << ' ' << smx << '\n';
            updmn(l, r, smx);
            continue;
        }
        int d = k / mxc, ex = k % mxc;
        if (ex == 0) {
            cerr << " UPDMN: " << l << ' ' << r << ' ' << mx - d << '\n';
            updmn(l, r, mx - d);
            k = 0;
            break;
        }
        int p = lb(l, mx, ex);
        cerr << " UPDMN: " << l << ' ' << p - 1 << ' ' << mx - d - 1 << '\n';
        cerr << " UPDMN: " << p << ' ' << r << ' ' << mx - d << '\n';
        assert(p <= r);
        updmn(l, p - 1, mx - d - 1);
        updmn(p, r, mx - d);
        k = 0;
    }
}
void magic(int i, int x) {
    cerr << "UPD " << i << ' ' << x << '\n';
    upd(i, x);
}
long long int inspect(int l, int r) {
    return qsm(l, r);
}

Compilation message

weirdtree.cpp: In function 'void propo(int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
weirdtree.cpp:47:5: note: in expansion of macro 'MLR'
   47 |     MLR;
      |     ^~~
weirdtree.cpp:42:17: warning: unused variable 'mid' [-Wunused-variable]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                 ^~~
weirdtree.cpp:47:5: note: in expansion of macro 'MLR'
   47 |     MLR;
      |     ^~~
weirdtree.cpp: In function 'void merge(int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
weirdtree.cpp:61:5: note: in expansion of macro 'MLR'
   61 |     MLR;
      |     ^~~
weirdtree.cpp:42:17: warning: unused variable 'mid' [-Wunused-variable]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                 ^~~
weirdtree.cpp:61:5: note: in expansion of macro 'MLR'
   61 |     MLR;
      |     ^~~
weirdtree.cpp: In function 'void init(int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
weirdtree.cpp:86:5: note: in expansion of macro 'MLR'
   86 |     MLR;
      |     ^~~
weirdtree.cpp: In function 'void upd(int, int, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
weirdtree.cpp:99:5: note: in expansion of macro 'MLR'
   99 |     MLR;
      |     ^~~
weirdtree.cpp: In function 'void updmn(int, int, int, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
weirdtree.cpp:118:5: note: in expansion of macro 'MLR'
  118 |     MLR;
      |     ^~~
weirdtree.cpp: In function 'iii qmx(int, int, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
weirdtree.cpp:132:5: note: in expansion of macro 'MLR'
  132 |     MLR;
      |     ^~~
weirdtree.cpp: In function 'll qsm(int, int, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
weirdtree.cpp:163:5: note: in expansion of macro 'MLR'
  163 |     MLR;
      |     ^~~
weirdtree.cpp: In function 'int lb(int, int, int&, int, int, int)':
weirdtree.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
weirdtree.cpp:179:5: note: in expansion of macro 'MLR'
  179 |     MLR;
      |     ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 56 ms 7544 KB Output is correct
4 Correct 71 ms 7544 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 472 ms 37216 KB Output is correct
4 Correct 322 ms 37328 KB Output is correct
5 Correct 434 ms 37196 KB Output is correct
6 Correct 314 ms 36988 KB Output is correct
7 Correct 8 ms 7124 KB Output is correct
8 Correct 36 ms 7200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7124 KB Output is correct
2 Correct 36 ms 7200 KB Output is correct
3 Correct 134 ms 28752 KB Output is correct
4 Correct 157 ms 28944 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 56 ms 7544 KB Output is correct
4 Correct 71 ms 7544 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 8 ms 7124 KB Output is correct
8 Correct 36 ms 7200 KB Output is correct
9 Correct 52 ms 9476 KB Output is correct
10 Correct 73 ms 9520 KB Output is correct
11 Correct 57 ms 9420 KB Output is correct
12 Correct 77 ms 9552 KB Output is correct
13 Correct 55 ms 9540 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 56 ms 7544 KB Output is correct
4 Correct 71 ms 7544 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 472 ms 37216 KB Output is correct
8 Correct 322 ms 37328 KB Output is correct
9 Correct 434 ms 37196 KB Output is correct
10 Correct 314 ms 36988 KB Output is correct
11 Correct 134 ms 28752 KB Output is correct
12 Correct 157 ms 28944 KB Output is correct
13 Correct 52 ms 9476 KB Output is correct
14 Correct 73 ms 9520 KB Output is correct
15 Correct 57 ms 9420 KB Output is correct
16 Correct 77 ms 9552 KB Output is correct
17 Correct 55 ms 9540 KB Output is correct
18 Correct 8 ms 7124 KB Output is correct
19 Correct 36 ms 7200 KB Output is correct
20 Correct 296 ms 36356 KB Output is correct
21 Correct 375 ms 36740 KB Output is correct
22 Correct 283 ms 36676 KB Output is correct
23 Correct 360 ms 36708 KB Output is correct
24 Correct 258 ms 36516 KB Output is correct