HackerEarth Levels of a tree problem solution

In this HackerEarth Levels of a tree problem solution, You are given a tree that consists of n vertex. In this tree, vertex 1 is the root vertex. Here, leveli is defined as a set of vertex where the distance of the vertexes from the root vertex is equal to i.

You are required to remove at most k levels of the tree in such a manner that after removing the vertexes, the maximum size of the recently-created components is minimum.

HackerEarth Levels of a tree problem solution.

`#include <bits/stdc++.h>using namespace std;#define int long longtypedef int ll;typedef long double ld;const ll N = 400005;char en = '\n';ll inf = 1e16;ll mod = 1e9 + 7;ll power(ll x, ll n, ll mod) {  ll res = 1;  x %= mod;  while (n) {    if (n & 1)      res = (res * x) % mod;    x = (x * x) % mod;    n >>= 1;  }  return res;}struct data {  // Use required attributes  int sum, left, right;  int len;  // Default Values  data() : sum(0), left(0), right(0), len(1){};};struct SegTree {  int N;  vector<data> st;  vector<bool> cLazy;  vector<int> lazy;  void init(int n) {    N = n;    st.resize(4 * N + 5);    cLazy.assign(4 * N + 5, false);    lazy.assign(4 * N + 5, 0);  }  // Write reqd merge functions  void merge(data &cur, data &l, data &r) {    cur.sum = max(l.sum, r.sum);    cur.sum = max(cur.sum, l.right + r.left);    cur.left = max(l.left, ((l.sum == l.len) ? (l.sum + r.left) : 0ll));    cur.right = max(r.right, ((r.sum == r.len) ? (r.sum + l.right) : 0ll));    cur.len = l.len + r.len;  }  // Handle lazy propagation appriopriately  void propagate(int node, int L, int R) {    if (L != R) {      cLazy[node * 2] = 1;      cLazy[node * 2 + 1] = 1;      lazy[node * 2] = lazy[node];      lazy[node * 2 + 1] = lazy[node];    }    st[node].sum = st[node].left = st[node].right = lazy[node];    cLazy[node] = 0;    lazy[node] = 0;  }  void build(int node, int L, int R) {    if (L == R) {      // st[node].mn = 1e9;      return;    }    int M = (L + R) / 2;    build(node * 2, L, M);    build(node * 2 + 1, M + 1, R);    merge(st[node], st[node * 2], st[node * 2 + 1]);  }  data Query(int node, int L, int R, int i, int j) {    if (cLazy[node])      propagate(node, L, R);    if (j < L || i > R)      return data();    if (i <= L && R <= j)      return st[node];    int M = (L + R) / 2;    data left = Query(node * 2, L, M, i, j);    data right = Query(node * 2 + 1, M + 1, R, i, j);    data cur;    merge(cur, left, right);    return cur;  }  data pQuery(int node, int L, int R, int pos) {    if (cLazy[node])      propagate(node, L, R);    if (L == R)      return st[node];    int M = (L + R) / 2;    if (pos <= M)      return pQuery(node * 2, L, M, pos);    else      return pQuery(node * 2 + 1, M + 1, R, pos);  }  void Update(int node, int L, int R, int i, int j, int val) {    if (cLazy[node])      propagate(node, L, R);    if (j < L || i > R)      return;    if (i <= L && R <= j) {      cLazy[node] = 1;      lazy[node] = val;      propagate(node, L, R);      return;    }    int M = (L + R) / 2;    Update(node * 2, L, M, i, j, val);    Update(node * 2 + 1, M + 1, R, i, j, val);    merge(st[node], st[node * 2], st[node * 2 + 1]);  }  void pUpdate(int node, int L, int R, int pos, int val) {    if (cLazy[node])      propagate(node, L, R);    if (L == R) {      cLazy[node] = 1;      lazy[node] = val;      propagate(node, L, R);      return;    }    int M = (L + R) / 2;    if (pos <= M)      pUpdate(node * 2, L, M, pos, val);    else      pUpdate(node * 2 + 1, M + 1, R, pos, val);    merge(st[node], st[node * 2], st[node * 2 + 1]);  }  data query(int pos) { return pQuery(1, 1, N, pos); }  data query(int l, int r) {    if (l > r)      return data();    return Query(1, 1, N, l, r);  }  void update(int pos, int val) { pUpdate(1, 1, N, pos, val); }  void update(int l, int r, int val) { Update(1, 1, N, l, r, val); }};struct Query {  ll L, R;  ll D;  ll indx;  Query() {}  Query(ll L, ll R, ll D, ll indx) : L(L), R(R), D(D), indx(indx) {}};int32_t main() {  ios_base::sync_with_stdio(false);  cin.tie(NULL);  ll n, q;  cin >> n >> q;  ll A[n + 5];  for (int i = 1; i <= n; i++) {    cin >> A[i];  }  ll diff[n + 5];  ll offset = 200000;  vector<ll> indicesList[400005];  for (ll i = 1; i < n; i++) {    diff[i] = A[i + 1] - A[i];    indicesList[offset + diff[i]].push_back(i);  }  vector<Query> queryEvent[400005];  for (ll i = 1; i <= q; i++) {    ll L, R, D;    cin >> L >> R >> D;    queryEvent[D + offset].push_back(Query(L, R, D, i));  }  ll ans[q + 5];  SegTree obj;  obj.init(n - 1);  for (ll i = 0; i <= 400000; i++) {    for (int indx : indicesList[i]) {      obj.update(indx, 1);    }    for (Query &query : queryEvent[i]) {      int indx = query.indx;      ans[indx] = obj.query(query.L, query.R - 1).sum + 1;    }    for (int indx : indicesList[i]) {      obj.update(indx, 0);    }  }  for (int i = 1; i <= q; i++)    cout << ans[i] << en;  return 0;}`

Second solution

`#include <bits/stdc++.h>using namespace std;#define int long longtypedef int ll;typedef long double ld;const ll N = 400005;char en = '\n';ll inf = 1e16;ll mod = 1e9 + 7;ll power(ll x, ll n, ll mod) {  ll res = 1;  x %= mod;  while (n) {    if (n & 1)      res = (res * x) % mod;    x = (x * x) % mod;    n >>= 1;  }  return res;}struct data {  // Use required attributes  int sum, left, right;  int len;  // Default Values  data() : sum(0), left(0), right(0), len(1){};};struct SegTree {  int N;  vector<data> st;  vector<bool> cLazy;  vector<int> lazy;  void init(int n) {    N = n;    st.resize(4 * N + 5);    cLazy.assign(4 * N + 5, false);    lazy.assign(4 * N + 5, 0);  }  // Write reqd merge functions  void merge(data &cur, data &l, data &r) {    cur.sum = max(l.sum, r.sum);    cur.sum = max(cur.sum, l.right + r.left);    cur.left = max(l.left, ((l.sum == l.len) ? (l.sum + r.left) : 0ll));    cur.right = max(r.right, ((r.sum == r.len) ? (r.sum + l.right) : 0ll));    cur.len = l.len + r.len;  }  // Handle lazy propagation appriopriately  void propagate(int node, int L, int R) {    if (L != R) {      cLazy[node * 2] = 1;      cLazy[node * 2 + 1] = 1;      lazy[node * 2] = lazy[node];      lazy[node * 2 + 1] = lazy[node];    }    st[node].sum = st[node].left = st[node].right = lazy[node];    cLazy[node] = 0;    lazy[node] = 0;  }  void build(int node, int L, int R) {    if (L == R) {      // st[node].mn = 1e9;      return;    }    int M = (L + R) / 2;    build(node * 2, L, M);    build(node * 2 + 1, M + 1, R);    merge(st[node], st[node * 2], st[node * 2 + 1]);  }  data Query(int node, int L, int R, int i, int j) {    if (cLazy[node])      propagate(node, L, R);    if (j < L || i > R)      return data();    if (i <= L && R <= j)      return st[node];    int M = (L + R) / 2;    data left = Query(node * 2, L, M, i, j);    data right = Query(node * 2 + 1, M + 1, R, i, j);    data cur;    merge(cur, left, right);    return cur;  }  data pQuery(int node, int L, int R, int pos) {    if (cLazy[node])      propagate(node, L, R);    if (L == R)      return st[node];    int M = (L + R) / 2;    if (pos <= M)      return pQuery(node * 2, L, M, pos);    else      return pQuery(node * 2 + 1, M + 1, R, pos);  }  void Update(int node, int L, int R, int i, int j, int val) {    if (cLazy[node])      propagate(node, L, R);    if (j < L || i > R)      return;    if (i <= L && R <= j) {      cLazy[node] = 1;      lazy[node] = val;      propagate(node, L, R);      return;    }    int M = (L + R) / 2;    Update(node * 2, L, M, i, j, val);    Update(node * 2 + 1, M + 1, R, i, j, val);    merge(st[node], st[node * 2], st[node * 2 + 1]);  }  void pUpdate(int node, int L, int R, int pos, int val) {    if (cLazy[node])      propagate(node, L, R);    if (L == R) {      cLazy[node] = 1;      lazy[node] = val;      propagate(node, L, R);      return;    }    int M = (L + R) / 2;    if (pos <= M)      pUpdate(node * 2, L, M, pos, val);    else      pUpdate(node * 2 + 1, M + 1, R, pos, val);    merge(st[node], st[node * 2], st[node * 2 + 1]);  }  data query(int pos) { return pQuery(1, 1, N, pos); }  data query(int l, int r) {    if (l > r)      return data();    return Query(1, 1, N, l, r);  }  void update(int pos, int val) { pUpdate(1, 1, N, pos, val); }  void update(int l, int r, int val) { Update(1, 1, N, l, r, val); }};struct Query {  ll L, R;  ll D;  ll indx;  Query() {}  Query(ll L, ll R, ll D, ll indx) : L(L), R(R), D(D), indx(indx) {}};int32_t main() {  ios_base::sync_with_stdio(false);  cin.tie(NULL);  ll n, q;  cin >> n >> q;  ll A[n + 5];  for (int i = 1; i <= n; i++) {    cin >> A[i];  }  ll diff[n + 5];  ll offset = 200000;  vector<ll> indicesList[400005];  for (ll i = 1; i < n; i++) {    diff[i] = A[i + 1] - A[i];    indicesList[offset + diff[i]].push_back(i);  }  vector<Query> queryEvent[400005];  for (ll i = 1; i <= q; i++) {    ll L, R, D;    cin >> L >> R >> D;    queryEvent[D + offset].push_back(Query(L, R, D, i));  }  ll ans[q + 5];  SegTree obj;  obj.init(n - 1);  for (ll i = 0; i <= 400000; i++) {    for (int indx : indicesList[i]) {      obj.update(indx, 1);    }    for (Query &query : queryEvent[i]) {      int indx = query.indx;      ans[indx] = obj.query(query.L, query.R - 1).sum + 1;    }    for (int indx : indicesList[i]) {      obj.update(indx, 0);    }  }  for (int i = 1; i <= q; i++)    cout << ans[i] << en;  return 0;}`