Submission #754785

#	Time	Username	Problem	Language	Result	Execution time	Memory
754785		maomao90	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	472 ms	37328 KiB

weirdtree

#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 (stderr)

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 / 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