# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

* Author:* Nguyen Ha Duy

*Shubham Anand Jain, Aryan*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

Easy-medium

# PREREQUISITES:

Segment Tree

# PROBLEM:

You are playing a game, where entering at time l and exiting at time r costs k\cdot (r-l) coins. You can enter and exit the game at most once.

There are n items in the game, the i th of them is valued at v_i coins, and can only be collected if l\leq x_i\leq y_i\leq r.

What is the maximum profit you can make?

# QUICK EXPLANATION:

- It is optimal to enter only at some x_i, and exit at some y_j.
- Consider all possible y_j in increasing order, and for each of them compute the maximum profit. The final answer is the maximum over all of these.
- Calculating the maximum profit can be done with any data structure supporting range max query and range sum updates, for example a segment tree.

# EXPLANATION:

First, note that it is optimal to exit only at some y_i - staying any longer would incur a cost of k coins for each unit of time, which is not optimal.

The same applies to entering - it is optimal to do so at some x_i.

**Subtask 1**

n \leq 20, so an \mathcal{O}(n\cdot 2^n) bruteforce over all possible subsets of items to choose will work fast enough.

Given a fixed non-empty set of items (x_{i_1}, y_{i_1}, v_{i_1}), \dotsc, (x_{i_r}, y_{i_r}, v_{i_r}), let L = min(x_{i_1}, x_{i_2}, \dotsc, x_{i_r}) and R = max(y_{i_1}, y_{i_2}, \dotsc, y_{i_r}). The maximum profit obtained while getting all of them is v_{i_1} + v_{i_2} + \dotsc + v_{i_r} - k\cdot (R-L).

Compute this value over all possible subsets and print the maximum of this and 0 (where we enter and exit at the same point and pick up nothing)

**Subtask 2**

Suppose, for the moment, that all the y_i are distinct.

Let us sort the items by y.

Now, for each 1\leq i\leq n,

Suppose we want to exit at y_i. Whatâ€™s the maximum profit possible?

Given that the items are sorted by increasing y, exiting at y_i means that itâ€™s impossible to pick up any of items i+1, i+2, \cdots, n, so we only need to worry about items 1, 2, \cdots, i.

Now suppose we enter at time x. Whatâ€™s the maximum profit?

- The cost of entering and exiting is k\cdot(y_i-x)
- For each 1\leq j\leq i, we can add v_j to the profit if x_j \geq x (because we know that y_j \leq y_i).

But, as mentioned before, itâ€™s enough to consider x to be one of the x_j where j\leq i, because entering at any other time cannot be optimal.

This gives an \mathcal{O}(n^3) solution: for each 1\leq i\leq n, iterate over 1\leq j\leq i and find out in \mathcal{O}(n) the maximum profit if we enter at x_j and leave at y_i. However, this is not fast enough to pass this subtask yet.

One can observe that this solution can be improved to O(n^2) by noting that, when we fix y_i, itâ€™s enough to traverse the x 's we have, in descending order. Doing that allows us to keep a running sum of the v_j which are possible to get, without needing a third loop to do so.

This can be implemented by, for example, keeping a sorted (multi)set of pairs (x_i, v_i). Iterating over this in descending order is easy, and insertion is \mathcal{O}(logN), leading to an overall O(n^2) solution.

How to deal with the fact that the y_i might not be distinct? Simply ignore it!

Even if theyâ€™re not all distinct, the above process will give the correct answer, simply because the maximum profit possible when exiting at any y will be calculated correctly when the last item with y_i = y is being processed.

**Subtask 3**

Quadratic is too slow here. Letâ€™s look at what weâ€™re actually computing.

The profit for entering at x and leaving at y_i is given by -k\cdot (y_i-x) + \displaystyle\sum_{\substack{1\leq j\leq i \\ x_j \geq x}} v_j

Rewrite this as -k*y_i + k*x + \displaystyle\sum_{\substack{1\leq j\leq i \\ x_j \geq x}} v_j.

k*y_i is a constant depending only on y_i, so we can ignore it for now.

What about the rest? It depends purely on x, so if we were able to update this value for each x after processing an item, maybe we could do something to get the maximum of them all.

And thatâ€™s exactly what we will do!

Suppose we had a really large array A, indexed by the integers -10^9 to 10^9.

Initially, let A[i] = k*i.

Whenever we process an item (x, y, v), do a range update and add v to the range [-10^9, x]

Now when we fix y_i and starting point x, whatâ€™s the cost of entering at x? It is exactly A[x] - k*y_i

So, our problem reduces to finding the maximum A[x] where x\leq y_i (equivalently, the max on the range [-10^9, y_i]), and being able to add a value to a range.

A segment tree with lazy propagation supports both these operations in logarithmic time, so that is our data structure of choice.

(Donâ€™t know how to perform these operations using a segment tree? Codeforces EDU is for you)

We are left with only one issue now: the initial array. It is way too big for us to explicitly create it, even if all subsequent operations on it are fast.

How to overcome this?

## Editorialist's Approach

The editorialist used a dynamic segment tree/implicit segment tree (click for more details), i.e, a segment tree where the only nodes created are the ones used in some query or update.

Since the only points we care about querying are the x_i, create an implicit segment tree with the values of all points set to -\infty. Then, for all x_i, set the value at x_i to be k\cdot x_i.

After this, update and query the tree as mentioned above, and the problem is done.

## Setter's Approach

The setter chose a different approach, and instead used coordinate compression. Map the smallest x_i to 1, the second smallest to 2, and so on. This maps all relevant points to [1, 10^5], and now we can build a normal segment tree on this array and update/query it as necessary. Finding the range to query/update requires binary search on the compressed coordinates.

Both methods use the fact that we only care about \mathcal{O}(N) points.

# TIME COMPLEXITY

\mathcal{O}(N\log{M}) or \mathcal{O}(N\log{N}) depending on implementation, where M = 2*10^9

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
const long long INF = 2e18;
const int maxN = 1e5 + 69;
struct items {
int x, y, v;
bool operator < (const items& oth) const {
return y < oth.y;
}
};
struct SegmentTree {
int n;
vector<long long> st;
vector<long long> lazy;
SegmentTree(int n) : n(n), st(n * 4, -INF), lazy(n * 4) {}
SegmentTree() {}
void change(long long v, int id) {
st[id] += v;
lazy[id] += v;
}
void push(int id) {
change(lazy[id], id * 2);
change(lazy[id], id * 2 + 1);
lazy[id] = 0;
}
void update(int L, int R, long long v, int id, int l, int r) {
if (R < l || r < L) return;
if (L <= l && r <= R) {
change(v, id);
return;
}
push(id);
int mid = (l + r) / 2;
update(L, R, v, id * 2, l, mid);
update(L, R, v, id * 2 + 1, mid + 1, r);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
void update(int L, int R, long long v) {
update(L, R, v, 1, 0, n);
}
};
int n, k;
int m;
items a[maxN];
vector<int> vals;
SegmentTree st;
int main() {
#define filename "BAI6"
// freopen("0.in.txt","r",stdin);
// std::ofstream outfile("output5.009", std::ios_base::binary | std::ios_base::out );
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y >> a[i].v;
vals.push_back(a[i].x);
vals.push_back(a[i].y);
}
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
m = vals.size();
sort(a + 1, a + 1 + n);
st = SegmentTree(m);
long long ans = 0;
int cur = 0;
for (int r = 0; r < m; r++) {
st.update(r, r, INF + 1ll * k * vals[r]);
while (cur + 1 <= n && a[cur + 1].y <= vals[r]) {
cur++;
if (a[cur].v > 0) {
int id = lower_bound(vals.begin(), vals.end(), a[cur].x) - vals.begin();
st.update(0, id, a[cur].v);
}
}
ans = max(ans, st.st[1] - 1ll * k * vals[r]);
}
cout << ans<<"\n";
}
```

## Tester's Solution

```
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define all(x) x.begin(),x.end()
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i=0;i<e;++i)
#define ln '\n'
typedef long long ll;
typedef pair<int,int> p32;
typedef vector<long long int> v64;
struct Segtree{
v64 t, lazy;
Segtree(int n) {
t.assign(4*n, -1e18);
lazy.assign(4*n, 0);
}
void build(long long int a[], int v, int tl, int tr){
if(tl == tr){
t[v] = a[tl];
}
else{
int tm = (tl + tr)/2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = max(t[v*2], t[v*2+1]);
}
}
void push(int v){
t[v*2] += lazy[v];
lazy[v*2] += lazy[v];
t[v*2+1] += lazy[v];
lazy[v*2+1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, long long int addend){
if(l > r){
return;
}
if(l <= tl && tr <= r){
t[v] += addend;
lazy[v] += addend;
} else {
push(v);
int tm = (tl + tr)/2;
update(v*2, tl, tm, l, min(r, tm), addend);
update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
t[v] = max(t[v*2], t[v*2+1]);
}
}
long long int query(int v, int tl, int tr, int l, int r) {
if(l>r) return -1e18;
if(l <= tl && tr <= r){
return t[v];
}
push(v);
int tm = (tl + tr)/2;
return max(query(v*2, tl, tm, l, min(r, tm)), query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
};
signed main(){
fastio;
long long int n, k;
cin>>n>>k;
vector<tuple<int,int>> events;
set<int> val;
tuple<int,int,int> things[n];
forn(i,n){
int x, y, v;
cin>>x>>y>>v;
events.push_back({y, i});
things[i] = {x, y, v};
val.insert(x);
val.insert(y);
}
sort(all(events));
map<int,int> to;
int cnt = 0;
forstl(r, val){
to[r] = cnt;
cnt++;
}
Segtree s(cnt);
long long int a[cnt];
forstl(r, val){
a[to[r]] = k * r;
}
s.build(a, 1, 0, cnt-1);
long long int ans = 0;
forstl(r, events){
long long int pt, ind;
tie(pt, ind) = r;
long long int x, y, v;
tie(x, y, v) = things[ind];
long long int get = s.query(1, 0, cnt-1, 0, to[x]) + v;
get -= k * y;
ans = max(ans, get);
s.update(1, 0, cnt-1, 0, to[x], v);
}
cout<<ans<<ln;
return 0;
}
```

## Editorialist's Solution

```
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
using namespace std;
using ll = long long;
struct Node {
typedef ll T;
static constexpr T unit = -2e18;
T f(T a, T b) { return max(a, b); }
Node *l = 0, *r = 0;
ll lo, hi, mset = unit, madd = 0;
T val = unit;
Node(int _lo,int _hi):lo(_lo),hi(_hi){}
T query(int L, int R) {
if (R <= lo || hi <= L) return unit;
if (L <= lo && hi <= R) return val;
push();
return f(l->query(L, R), r->query(L, R));
}
void set(int L, int R, T x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) mset = val = x, madd = 0;
else {
push(), l->set(L, R, x), r->set(L, R, x);
val = f(l->val, r->val);
}
}
void add(int L, int R, T x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
if (mset != unit) mset += x;
else madd += x;
val += x;
}
else {
push(), l->add(L, R, x), r->add(L, R, x);
val = f(l->val, r->val);
}
}
void push() {
if (!l) {
int mid = lo + (hi - lo)/2;
l = new Node(lo, mid); r = new Node(mid, hi);
}
if (mset != unit)
l->set(lo,hi,mset), r->set(lo,hi,mset), mset = unit;
else if (madd)
l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
}
};
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, k; cin >> n >> k;
Node *tr = new Node(-1000000007, 1000000007);
vector<array<int, 3>> a(n);
for (auto &[x, y, v] : a) {
cin >> x >> y >> v;
tr -> set(x, x+1, 1LL*k*x);
tr -> set(y, y+1, 1LL*k*y);
}
sort(begin(a), end(a), [](auto x, auto y){return x[1] < y[1];});
ll ans = 0;
for (auto [x, y, v] : a) {
// Best answer ending at y, with everything considered so far
tr -> add(-1000000007, x+1, v);
ans = max(ans, tr->query(-1000000007, y+1)-1LL*k*y);
}
cout << ans << '\n';
}
```