oj.uz

Submission #744161

# Submission time Handle Problem Language Result Execution time Memory
744161 2023-05-18T08:50:18 Z maomao90 Weirdtree (RMI21_weirdtree) C++17
13 / 100
 121 ms 24340 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];
ii mx[MAXN * 4];
#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
void init(int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        sm[u] = h[lo];
        mx[u] = {h[lo], -lo};
        return;
    }
    MLR;
    init(lc, lo, mid);
    init(rc, mid + 1, hi);
    sm[u] = sm[lc] + sm[rc];
    mx[u] = max(mx[lc], mx[rc]);
}
void upd(int p, int x, int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        sm[u] = x;
        mx[u].FI = x;
        return;
    }
    MLR;
    if (p <= mid) {
        upd(p, x, lc, lo, mid);
    } else {
        upd(p, x, rc, mid + 1, hi);
    }
    sm[u] = sm[lc] + sm[rc];
    mx[u] = max(mx[lc], mx[rc]);
}
ll qsm(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        return sm[u];
    }
    ll res = 0;
    MLR;
    if (s <= mid) {
        res += qsm(s, e, lc, lo, mid);
    }
    if (e > mid) {
        res += qsm(s, e, rc, mid + 1, hi);
    }
    return res;
}
ii qmx(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        return mx[u];
    }
    ii res = {-INF, -INF};
    MLR;
    if (s <= mid) {
        mxto(res, qmx(s, e, lc, lo, mid));
    }
    if (e > mid) {
        mxto(res, qmx(s, e, rc, mid + 1, hi));
    }
    return res;
}

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) {
    ii mx = qmx(l, r);
    cerr << ' ' << mx.FI << ' ' << mx.SE << '\n';
    if (mx.FI != 0) {
        upd(-mx.SE, mx.FI - 1);
    }
}
void magic(int i, int x) {
    upd(i, x);
}
long long int inspect(int l, int r) {
    return qsm(l, r);
}

Compilation message

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:49:5: note: in expansion of macro 'MLR'
   49 |     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:61:5: note: in expansion of macro 'MLR'
   61 |     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:75:5: note: in expansion of macro 'MLR'
   75 |     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:89:5: note: in expansion of macro 'MLR'
   89 |     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 40 ms 7448 KB Output is correct
4 Correct 42 ms 7388 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 24208 KB Output is correct
2 Correct 121 ms 24340 KB Output is correct
3 Incorrect 22 ms 7164 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 40 ms 7448 KB Output is correct
4 Correct 42 ms 7388 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 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 40 ms 7448 KB Output is correct
4 Correct 42 ms 7388 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -