oj.uz

Submission #754757

# Submission time Handle Problem Language Result Execution time Memory
754757 2023-06-08T13:41:16 Z maomao90 Weirdtree (RMI21_weirdtree) C++17
15 / 100
 173 ms 28872 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);
}
ii qmx(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        return {mx[u], mxc[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 {
        ii lmx = qmx(s, e, lc, lo, mid),
           rmx = qmx(s, e, rc, mid + 1, hi);
        if (lmx.FI == rmx.FI) {
            lmx.SE += rmx.SE;
            return lmx;
        }
        return max(lmx, rmx);
    }
}
ii qsmx(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        return {mx[u], smx[u]};
    }
    MLR;
    propo(u, lo, hi);
    if (e <= mid) {
        return qsmx(s, e, lc, lo, mid);
    } else if (s > mid) {
        return qsmx(s, e, rc, mid + 1, hi);
    } else {
        ii lmx = qsmx(s, e, lc, lo, mid),
           rmx = qsmx(s, e, rc, mid + 1, hi);
        ii res;
        if (lmx.FI == rmx.FI) {
            res.FI = lmx.FI;
            res.SE = max(lmx.SE, rmx.SE);
        } else if (lmx.FI > rmx.FI) {
            res.FI = lmx.FI;
            res.SE = max(lmx.SE, rmx.FI);
        } else {
            res.FI = rmx.FI;
            res.SE = max(rmx.SE, lmx.FI);
        }
        return res;
    }
}
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) {
        return lo;
    }
    MLR;
    propo(u, lo, hi);
    if (mid < s) {
        return lb(s, x, c, rc, mid + 1, hi);
    } else if (lo < s) {
        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, smx] = qsmx(l, r);
        auto [_, mxc] = qmx(l, r);
        cerr << mx << ' ' << smx << ' ' << mxc << '\n';
        assert(_ == mx);
        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) {
            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 'ii 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 'ii qsmx(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:152:5: note: in expansion of macro 'MLR'
  152 |     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:180:5: note: in expansion of macro 'MLR'
  180 |     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:195:5: note: in expansion of macro 'MLR'
  195 |     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
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 64 ms 7532 KB Output is correct
4 Incorrect 82 ms 8504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 28836 KB Output is correct
2 Correct 173 ms 28872 KB Output is correct
3 Correct 8 ms 7124 KB Output is correct
4 Correct 35 ms 7124 KB Output is correct

Subtask #6
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 64 ms 7532 KB Output is correct
4 Incorrect 82 ms 8504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
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 64 ms 7532 KB Output is correct
4 Incorrect 82 ms 8504 KB Output isn't correct
5 Halted 0 ms 0 KB -