A Simple Introduction to CDQ Divide and Conquer

Outline

• What is CDQ D&C?
• Example problems
  • ZJc571 - Three-dimensional partial order problem
  • BZOJ1176 - Mokia
  • BZOJ3295 - Dynamic Inversion Pairs
  • CF1093E - Intersection of Permutations
  • TIOJ1921 - ATM2
• More problems

What is CDQ D&C?

CDQ D&C is a offline technique invented by a China competitive programmer (called CDQ, obviously). CDQ D&C is almost same to normal D&C. The biggest difference between them is that suppose we cut a interval $[l, r)$ into $[l, m), [m, r)$. In normal D&C, the elements from $[l, m)$ won’t influence $[m, r)$; In CDQ D&C, elemenst from $[l, m)$ will influence $[m, r)$. Therefore, the framework of CDQ D&C usually looks like this.

1. Divide $[l, r)$ into $[l, m), [m, r)$.
2. Solve two subproblems $[l, m), [m, r)$.
3. Calculate the influence of $[l, m)$ on $[m, r)$.
4. Merge $[l, m), [m, r)$.

As the introduction above might be to abstract, let’s dive into problems below to get more “feeling” about it. We’ll abbreviate CDQ D&C to CDQ.

Example problems

ZJc571 - Three-dimensional partial order problem (Chinese)

Problem description

You’re given a set of unique three-dimension points $S$ with size $n$. For each point $P_i=(x_i, y_i, z_i)\in S$, please calculate the number of points $P_j\in S$ such that $x_i<x_j, y_i<y_j, z_i<z_j$.

$1\le n\le 10^5, 1\le x_i, y_i, z_i\le 10^5$

Problem analysis

First, this problem is solvable with any comparator with that have transitivity ($<, >, \le, \ge\dots$). Formally, they’re called partial order. This math version of this problem is $\sum\limits_{x_i< x_j, y_i< y_j, z_i<x_j} 1$.

This problem is a classic problem that CDQ can deal with. Let’s look at an easier problem first: Given an array $A$, please calculate the number of inversion pairs. There’re lots of ways to do it, one of it (which we will use) is given here.

What’s the connection between counting inversion pairs with the original problem? Counting inversion pairs is a Two-dimensional partial order problem! For every element $A_i$ at position $i$, if we view it as $(i, A_i)$, then number of inversion paris that ends with $i$ is exactly number of $(j, A_j)$ such that $j<i, A_j>A_i$.

So now we know how to solve Two-dimensional partial order problem. Then, we can solve Three-dimensional partial order problem by reducing it to Two-dimension using CDQ.

Problem solution

We reduce it by the following steps:

1. Sort one of the axes. Let’s sort $x$ axis here.
2. Suppose that we’ll dealing with $[l, r)$. Split it into two subproblems $[l, m), [m, r)$ and deal with it recursively.
3. Note that “calculate influence of $[l, m)$ to $[m, r)$” is a Two-dimensional partial order problem because:
   1. We only need to consider whether each element in $[l, m)$ is a part of answer of each element in $[m, r)$ or not. This implies that order of $x_i$ in $[l, m)$ is not important.
   2. $x$ axis in $[l, m)$ is greater $[m, r)$ i.e. $\min_{i\in [l, m)}x_i\ge \max_{i\in [m, r)}x_i$, we successfully reduced the original problem to Two-dimension version.
4. Solve the Two-dimensional partial order problem by sorting $[l, r)$ with $y_i$ and BIT.

By appling Master Theorem to $T(N)=2T(\frac{N}{2})+O(N\log N)$ we can get the complexity $O(N\log^2 N)$. There’re serveral important details given in the code.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Pt {
  int x, y, z, i;
};

const int N = (int)1e5 + 5;

struct BIT {
  int b[N], n;

  void init(int _n) {
    n = _n;
    for(int i = 0 ; i <= n ; ++i) b[i] = 0;
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, int v) {
    for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  int query(int x) {
    int ans = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
    return ans;
  }
} bit;

vector<Pt> v;
int n, ans[N];

void cdq(int l, int r) {
  if(l + 1 == r) return;
  int m = (l + r) >> 1;
  cdq(l, m); cdq(m, r);
  int a = l, b = m, sum = 0;
  // need to record the modifications on BIT in order to reset it. The complexity will be $O(N^2)$ if we resetting it brute-forcely.
  vector<int> record;
  // temporary array for merge sort
  vector<Pt> tmp;
  while(a < m && b < r) {
    if(v[a].y > v[b].y) bit.update(v[a].z, 1), sum++, record.push_back(v[a].z), tmp.push_back(v[a++]);
    else ans[v[b].i] += sum - bit.query(v[b].z), tmp.push_back(v[b++]);
  }
  while(a < m) tmp.push_back(v[a++]);
  while(b < r) ans[v[b].i] += sum - bit.query(v[b].z), tmp.push_back(v[b++]);
  for(int i = l ; i < r ; ++i) v[i] = tmp[i - l];
  // reset BIT
  for(auto i : record) bit.update(i, -1);
  // release used memory
  vector<int> ().swap(record);
  vector<Pt> ().swap(tmp);
}

void init() {
  cin >> n;
  for(int i = 0 ; i < n ; ++i) {
    int a, b, c; cin >> a >> b >> c;
    v.push_back({a, b, c, i});
  }
  bit.init(n);
}
void solve() {
  // As we require > not >=
  sort(v.begin(), v.end(), [&](auto a, auto b) { 
      return (a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x > b.x); 
  }); 
  cdq(0, n);
  for(int i = 0 ; i < n ; ++i) cout << ans[i] << '\n';
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  init();
  solve();
}

BZOJ1176 - Mokia (Chinese)

Problem description

You’re given a square matrix $A$ with size $W\times W$, all elements in $A$ are initialized with $S$. You need to handle $Q$ operations of two kinds:

• $1\space x\space y\space a$: Increase $A_{x, y}$ by $a$.
• $2\space x_1\space y_1\space x_2\space y_2$: Calculate the sum of submatrix $A’$ with $(x_1, y_1)$ being the upper-left corner and $(x_2, y_2)$ being the bottom-right corner.

$1\le W\le 2\times 10^6, 1\le Q\le 10^4$

Problem analysis

This problem doesn’t seem to have any connection to CDQ. Let’s try to transform it.

1. the second operation can be calculated using four prefix sum.
2. Prefix sum is similar to partial order problem: prefix sum at $(x, y)$ is $\sum\limits_{i\le x, j\le y}A_{i, j}$.

Using the observation above, we can view the two operations in this problem as elements $(t, x, y)$ ($t$ is the time of the operation), and solve it with the method silimar to the previous problem.

Problem solution

• For type $1$ operations, create element $(t, x, y)$ with value $a$.
• For type $2$ operations, create element $(t, x_2, y_2), (t, x_1-1, y_2), (t, x_2, y_1-1), (t, x_1-1, y_1-1)$.

For $(t, x, y), \sum\limits_{(k, i, j) | k<t,i\le x, j\le y}A_{i, j}$ is exactly the prefix sum at time $t$. The complexity is $O(Q\log Q\log W)$.

See code for more details.

code

#include <iostream>
#include <vector>
#define F first
#define S second
using namespace std;
typedef long long ll;

const int N = (int)2e6 + 5;

namespace bit {
  ll b[N], n;

  void init(int _n) {
    n = _n;
    fill(b, b + n + 1, 0);
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, int v) {
    if(x == 0) return;
    for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  ll query(int x) {
    ll ans = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
    return ans;
  }
}
struct Node {
  int t, x, y, v, i, sgn;
};

vector<Node> v;
vector<ll> ans;
int s, w;

void cdq(int l, int r) {
  if(l + 1 == r) return;
  int m = (l + r) >> 1;
  cdq(l, m); cdq(m, r);
  vector<Node> tmp;
  vector<pair<int, ll> > his;
  int a = l, b = m;
  while(a < m && b < r) {
    if(v[a].x <= v[b].x) {
      bit::update(v[a].y, v[a].v);
      his.push_back({v[a].y, -v[a].v});
      tmp.push_back(v[a++]);
    }
    else {
      ans[v[b].i] += v[b].sgn * (bit::query(v[b].y) + (ll)s * v[b].x * v[b].y);
      tmp.push_back(v[b++]);
    }
  }
  while(a < m) tmp.push_back(v[a++]);
  while(b < r) {
    ans[v[b].i] += v[b].sgn * (bit::query(v[b].y) + (ll)s * v[b].x * v[b].y);
    tmp.push_back(v[b++]);
  }
  for(int i = l ; i < r ; ++i) v[i] = tmp[i - l];
  for(int i = 0 ; i < (int)his.size() ; ++i) bit::update(his[i].F, his[i].S);
  vector<Node> ().swap(tmp);
  vector<pair<int ,ll> > ().swap(his);
}

void init() {
  cin >> s >> w;
  bit::init(w);
  v.clear(); ans.clear();
  ans.push_back(0);
  int op, i = 0; cin >> op;
  while(op != 3) {
    if(op == 1) {
      int x, y, a; cin >> x >> y >> a;
      v.push_back({i, x, y, a, 0, 0});
    }
    else {
      int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
      v.push_back({i, x1 - 1, y1 - 1, 0, (int)ans.size(), 1});
      v.push_back({i, x1 - 1, y2, 0, (int)ans.size(), -1});
      v.push_back({i, x2, y1 - 1, 0, (int)ans.size(), -1});
      v.push_back({i, x2, y2, 0, (int)ans.size(), 1});
      ans.push_back(0);
    }
    cin >> op, ++i;
  }
}
void solve() {
  cdq(0, (int)v.size());
  for(int i = 1 ; i < (int)ans.size() ; ++i) cout << ans[i] << '\n';
}


int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  init();
  solve();
}

BZOJ3295 - Dynamic Inversion Pairs (Chinese)

Problem description

You’re given $N$ and $A$, permutation of $1, 2, \dots, N$. You need to support $M$ operations, where in every operation you need to calculate number of inversion pairs and delete an element from the $A$. A inversion pair $(i, j), 1\le i, j, \le N$ is a pair that satisfies $i < j$ and $A_i>A_j$.

$1\le N\le 10^5, 1\le M\le 5\times 10^4$

Problem analysis

We already know that counting inversion pairs is a Two-dimensional partial order problem. However, in this problem we need to support “delete” operations. This can be handled by adding a dimension: valid time of the element. After adding it, this problem is reduced into a Three-dimensional partial order problem, and can be solved with similar ways from above.

Problem solution

For every delete operations, add element $(t, val, pos)$. Then, for element $(t, val, pos), \sum\limits_{(k, i, j) | k>t,i>val, j<pos}1 + \sum\limits_{(k, i, j) | k>t,i<val, j>pos}1$ is exactly the number of inversion pairs related to the element at $pos$. The two terms can be calculated using two CDQs, and the time complexity will be $O(N\log^2 N)$. More details in code.

code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = (int)1e5 + 5;

namespace bit {
  ll n, b[N];
  
  void init(int _n) {
    n = _n;
    fill(b, b + n + 1, 0);
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, int v) {
    for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  ll query(int x) {
    ll ans = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
    return ans;
  }
}
struct Node {
  int t, v, id, i;

  bool operator<(const Node& rhs) const { return t > rhs.t; }
};

vector<Node> Q;
vector<ll> ans;
ll invcnt;

void cdq(int l, int r, int op) {
  if(l + 1 == r) return;
  int m = (l + r) >> 1;
  cdq(l, m, op); cdq(m, r, op);
  vector<Node> tmp;
  vector<int> his;
  int a = l, b = m, sum = 0;
  while(a < m && b < r) {
    if((!op && Q[a].v > Q[b].v) || (op && Q[a].v < Q[b].v)) {
      bit::update(Q[a].id, 1), sum++;
      his.push_back(Q[a].id);
      tmp.push_back(Q[a++]);
    }
    else {
      ans[Q[b].i] += (op ? sum : 0) - (op ? 1 : -1) * bit::query(Q[b].id);
      tmp.push_back(Q[b++]);
    }
  }
  while(a < m) tmp.push_back(Q[a++]);
  while(b < r) {
    ans[Q[b].i] += (op ? sum : 0) - (op ? 1 : -1) * bit::query(Q[b].id);
    tmp.push_back(Q[b++]);
  }
  for(int i = l ; i < r ; ++i) Q[i] = tmp[i - l];
  for(int i = 0 ; i < (int)his.size() ; ++i) bit::update(his[i], -1);
  vector<Node> ().swap(tmp);
  vector<int> ().swap(his);
}

void init() {
  int n, m; cin >> n >> m;
  vector<int> v(n + 1), pos(n + 1);
  for(int i = 1 ; i <= n ; ++i) cin >> v[i], pos[v[i]] = i;
  // get initial invcnt
  bit::init(n);
  invcnt = 0; int sum = 0;
  for(int i = 1 ; i <= n ; ++i) {
    invcnt += sum - bit::query(v[i]);
    bit::update(v[i], 1), sum++;
  }
  bit::init(n);
  // process query
  ans.push_back(0);
  for(int i = 0 ; i < m ; ++i) {
    int x; cin >> x;
    Q.push_back({i, x, pos[x], i + 1});
    ans.push_back(0);
    pos[x] = 0;
  }
  for(int i = 1 ; i <= n ; ++i) if(pos[i]) Q.push_back({m, i, pos[i], 0});
}
void solve() {
  sort(Q.begin(), Q.end());
  cdq(0, (int)Q.size(), 0);
  sort(Q.begin(), Q.end());
  cdq(0, (int)Q.size(), 1);
  for(int i = 1 ; i < (int)ans.size() ; ++i) {
    cout << invcnt << '\n';
    invcnt -= ans[i];
  }
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  init();
  solve();
}

CF1093E - Intersection of Permutations

Problem description

You are given two permutations $a$, $b$, both consisting of $N$ elements. You need to support $M$ operations of two kinds:

• $1\space l_a\space r_a\space l_b\space r_b$: calculate the number of values which appear in both segment $[l_a, r_a]$ of positions in permutation $a$ and segment $[l_b, r_b]$ of positions in permutation $b$.
• $2\space x\space y$: swap values on position $x$ and $y$ in permutation $b$.

$2\le N\le 2\times 10^5, 1\le M\le 2\times 10^5$

Problem analysis

As both sequence are permutations from $[1, N]$, we can given each element $i\in[1, N]$ a “coordinate”: (position of $i$ in $a$, position of $i$ in $b$). Then, type 1 operation can be viewed as “prefix sum” from $(l_a, l_b)$ to $(r_a, r_b)$, and type 2 operations can be viewed as modifying values at position $(x, y)$. Then, this problem is similar to Mokia, which can be solved by CDQ.

Problem solution

The time complexity is $O(M\log M\log N)$. Details are given in the code.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = (int)2e5 + 5;

namespace bit {
  int n, b[N];

  void init(int _n) {
    n = _n;
    fill(b, b + n + 1, 0);
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, int v) {
    if(x == 0) return;
    for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  int query(int x) {
    int ans = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
    return ans;
  }
}
struct Node {
  int t, x, y, i, sgn, v;
};

vector<Node> Q;
vector<int> ans;

void cdq(int l, int r) {
  if(l + 1 == r) return;
  int m = (l + r) >> 1;
  cdq(l, m); cdq(m, r);
  vector<Node> tmp;
  vector<pair<int, int> > his;
  int a = l, b = m;
  while(a < m || b < r) {
    if(b == r || (a < m && Q[a].x <= Q[b].x)) {
      bit::update(Q[a].y, Q[a].v);
      his.push_back({Q[a].y, Q[a].v});
      tmp.push_back(Q[a++]);
    }
    else {
      ans[Q[b].i] += Q[b].sgn * bit::query(Q[b].y);
      tmp.push_back(Q[b++]);
    }
  }
  for(auto [x, v] : his) bit::update(x, -v);
  for(int i = l ; i < r ; ++i) Q[i] = tmp[i - l];
  vector<Node> ().swap(tmp);
  vector<pair<int, int> > ().swap(his);
}

void init() {
  int n, m; cin >> n >> m;
  bit::init(n);
  vector<int> a(n + 1), b(n + 1), pos(n + 1);
  for(int i = 1 ; i <= n ; ++i) cin >> a[i], pos[a[i]] = i;
  for(int i = 1 ; i <= n ; ++i) cin >> b[i];
  Q.clear();
  ans.push_back(0);
  for(int i = 1 ; i <= n ; ++i) Q.push_back({(int)Q.size(), pos[b[i]], i, 0, 0, 1});
  while(m--) {
    int op; cin >> op;
    if(op == 1) {
      int la, ra, lb, rb; cin >> la >> ra >> lb >> rb;
      Q.push_back({(int)Q.size(), ra, rb, (int)ans.size(), 1, 0});
      Q.push_back({(int)Q.size(), la - 1, rb, (int)ans.size(), -1, 0});
      Q.push_back({(int)Q.size(), ra, lb - 1, (int)ans.size(), -1, 0});
      Q.push_back({(int)Q.size(), la - 1, lb - 1, (int)ans.size(), 1, 0});
      ans.push_back(0);
    }
    else {
      int x, y; cin >> x >> y;
      Q.push_back({(int)Q.size(), pos[b[x]], x, 0, 0, -1});
      Q.push_back({(int)Q.size(), pos[b[y]], y, 0, 0, -1});
      swap(b[x], b[y]);
      Q.push_back({(int)Q.size(), pos[b[x]], x, 0, 0, 1});
      Q.push_back({(int)Q.size(), pos[b[y]], y, 0, 0, 1});
    }
  }
}
void solve() {
  cdq(0, (int)Q.size());
  for(int i = 1 ; i < (int)ans.size() ; ++i) cout << ans[i] << '\n';
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  init();
  solve();
}

TIOJ1921 - ATM2 (Chinese)

Problem description

You want to make a fortune by purchasing, selling, and of course, using cash printing machine (CPM). Now, every day is divided to three parts: morning(912), afternoon(1318), and night(19~22). In the morning, you can sell CPM that you’ve purchased before. In the afternoon, you can use your CPM to print cash. At night, you can purchase a new CPM. Note that you cannot have two CPM at the same time i.e. before purchasing a new CPM, you must sell your old CPM.

You are given information of $N$ CPMs. For the $i^{th}$ CPM, it can only be bought at day $D_i$ with price $P_i$, and it can be sold with price $R_i$. It can print $G_i$ cash every day. Now you’re given $C$ dollars in the beginning, please maximize the cash you can earn in $D$ days i.e. maximize the cash you can have at 12 o’clock of day $D+1$.

$N\le 10^5, C, D, G_i\le 10^9, D_i\le D, R_i<P_i\le 10^9$

Problem analysis

This problem is actually a DP problem, and can be solved in $O(N\log N)$ using convex-hull optimization. Let $dp_i$ represent the maximum cash you can have after buying the $i^{th}$ machine, then $$ dp_i=\max_{0\le j < i, dp_j\ge 0} \left\{dp_j + (D_i - D_j -1)\times G_j + R_j - P_i\right\} $$ , which can be rewritten to: $$ dp_i=\max_{0\le j < i, dp_j\ge 0} \left\{G_jD_i + dp_j + R_j - (D_j+1)\times G_j\right\} - P_i $$ If we view $a_j=G_j$, $b_j=dp_j + R_j - (D_j+1)\times G_j$, then: $$ dp_i=\max_{0\le j < i, dp_j\ge 0} \left\{a_jD_i + b_j\right\} - P_i $$ which is exactly the form of convex-hull optimization. Here’s the code using dynamic convex hull to solve it:

code

#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target ("sse,sse2,sse3,ssse3,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll is_query = -(1LL<<62);
struct Line {
  ll m, b;
  mutable function<const Line*()> succ;
  bool operator<(const Line& rhs) const {
    if (rhs.b != is_query) return m < rhs.m;
    const Line* s = succ();
    return s ? b - s->b < (s->m - m) * rhs.m : 0;
  }
}; // maintain upper hull for maximum
struct HullDynamic : public multiset<Line> {
  bool bad(iterator y) {
    auto z = next(y);
    if (y == begin()) {
      if (z == end()) return 0;
      return y->m == z->m && y->b <= z->b;
    }
    auto x = prev(y);
    if(z==end())return y->m==x->m&&y->b<=x->b;
    return (x->b-y->b)*(z->m-y->m)>=
            (y->b-z->b)*(y->m-x->m);
  }
  void insert_line(ll m, ll b) {
    auto y = insert({m, b});
    y->succ = [=]{return next(y)==end()?0:&*next(y);};
    if(bad(y)) {erase(y); return; }
    while(next(y)!=end()&&bad(next(y)))erase(next(y));
    while(y!=begin()&&bad(prev(y)))erase(prev(y));
  }
  ll eval(ll x) {
    auto l = *lower_bound((Line) {x, is_query});
    return l.m * x + l.b;
  }
} hull;

struct ATM {
  ll d, p, r, g;
};

ll n, c, d, dp;
vector<ATM> atm;

void init() {
  cin >> n >> c >> d; atm.resize(n);
  for(int i = 0 ; i < n ; ++i) {
    cin >> atm[i].d >> atm[i].p >> atm[i].r >> atm[i].g;
  }
  sort(atm.begin(), atm.end(), [&](auto a, auto b) { return a.d < b.d; });
}
void solve() {
  hull.insert_line(0, c);
  for(int i = 0 ; i < n ; ++i) {
    dp = hull.eval(atm[i].d) - atm[i].p;
    if(dp >= 0) hull.insert_line(atm[i].g, dp + atm[i].r - atm[i].g * (atm[i].d + 1));
  }
  cout << hull.eval(d + 1) << '\n';
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  init();
  solve();
}

However, we can solve this problem with CDQ, which is easier if you forgot how to write dynamic convex hull during contest :).

Problem solution

For dp values in $[l, r)$:

1. Calculate dp values recursively in $[l, m)$.
2. Use dp values in $[l, m)$ to update $[m, r)$.
3. Calculate dp values recursively in $[m, r)$.
4. Merge two convex hull: One from $[l, m)$, and another from $[m, r)$. This can be easily done with a std::vector as the slope is increasing.

The complexity is $O(N\log N)$ as the merging part only takes $O(N)$. See details in code.

code

#pragma GCC optimize ("O3,unroll-loops,no-stack-protector")
#pragma GCC target ("avx,avx2")
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;

struct ATM {
  ll d, p, r, g;
};

const int N = (int)1e5 + 5;
const ll inf = (ll)1e19;

ll n, c, d, dp[N];
vector<ATM> atm;

ll eval(pair<ll, ll>& p, ll v) {
  return p.F * v + p.S;
}
bool check(pair<ll, ll>& a, pair<ll, ll>& b, pair<ll, ll>& c) {
  return (__int128)(b.S - a.S) * (b.F - c.F) <= (__int128)(c.S - b.S) * (a.F - b.F);
}
void add(vector<pair<ll, ll> >& v, pair<ll, ll> l) {
  while((int)v.size() >= 2 && check(l, v[v.size() - 1], v[v.size() - 2])) v.pop_back();
  v.push_back(l);
}
vector<pair<ll, ll> > cdq(int l, int r) {
  if(l + 1 == r) {
    if(dp[l] >= 0) return ;
    else return {};
  }
  int m = (l + r) >> 1;
  vector<pair<ll, ll> > l1 = cdq(l, m);
  for(int i = m, j = 0 ; l1.size() && i < r ; ++i) {
    while(j + 1 < (int)l1.size() && eval(l1[j], atm[i].d) < eval(l1[j + 1], atm[i].d)) ++j;
    dp[i] = max(dp[i], eval(l1[j], atm[i].d) - atm[i].p);
  }
  vector<pair<ll, ll > > l2 = cdq(m, r);
  vector<pair<ll, ll > > l3;
  int a = 0, b = 0;
  while(a < (int)l1.size() && b < (int)l2.size()) {
    if(l1[a] < l2[b]) add(l3, l1[a++]);
    else add(l3, l2[b++]);
  }
  while(a < (int)l1.size()) add(l3, l1[a++]);
  while(b < (int)l2.size()) add(l3, l2[b++]);
  vector<pair<ll, ll> > ().swap(l1);
  vector<pair<ll, ll> > ().swap(l2);
  return l3;
}

void init() {
  cin >> n >> c >> d; atm.resize(n + 2);
  atm[0] = {0, 0, c, 0};
  for(int i = 1 ; i <= n ; ++i) {
    cin >> atm[i].d >> atm[i].p >> atm[i].r >> atm[i].g;
  }
  atm[n + 1] = {d + 1, 0, 0, 0};
  sort(atm.begin(), atm.end(), [&](auto a, auto b) { return a.d < b.d; });
}
void solve() {
  fill(dp, dp + n + 2, -inf);
  dp[0] = 0;
  cdq(0, n + 2);
  cout << dp[n + 1] << '\n';
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  init();
  solve();
}

More problems

• CF293E - Close Vertices
• BZOJ4836 - Binary Operation