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 long
typedef 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 long
typedef 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;
}
0 Comments