(Analysis by Benjamin Qi, Brandon Wang, Claire Zhang)

Let us first suppose we compute each $e_n$ separately, and then we will do this $D$ times. (Later we will describe how to support updates.) Suppose $(m_1, b_1), \ldots, (m_n, b_n)$ are in increasing order of $m_i$. We can make the following observations:

  1. If $b_i \geq b_j$ for $i < j$, then we can ignore demand $j$.
  2. Let us suppose we create $a_i$ tasks on day $i$. Then, we can assume $a_1 \geq a_2 \geq a_3 \cdots$ (since if $a_i < a_j$ with $i > j$, we can swap $a_i$ and $a_j$).

Subtask 1 ($D\le100$, $m_i \le 100$):

Let the cost of a sequence of increments $(a_i)$ be the energy required $\left(\sum_i 3^{a_i}\right)$. Additionally, say $(a_i)$ is valid if it satisfies all demands.

Claim: The lexicographically minimal sequence $(a_i)$ which is non-increasing and valid attains minimum cost.

Proof: Let $(a_i)$ be the lexicographically minimal sequence which is non-increasing and valid. Suppose for sake of contradiction that the lowest-cost non-increasing, valid sequence $(b_i)$ has lower cost than $(a_i)$. Without loss of generality, say the first index $i$ where $a_i\ne b_i$ is $i=1$. For example, consider

$(a_i) = [4, 4, 4, 4, 2]$

$(b_i) = [5, 5, 4, 3, 1]$

Then we claim $(b_i)$ is not the lowest-cost sequence which is non-increasing and valid: consider decrementing $b_j$, where $j$ is maximum index such that $b_j=b_1$, and incrementing $b_k$, where $k$ is the minimum index such that $b_k \le b_1-2$ (if such exists). In the example,

$(b_i) = [5, 5, 4, 3, 1] \rightarrow (b'_i) = [5, 5-1, 4, 3+1, 2]$


$(b'_i)$ is a valid, non-increasing, sequence with lower cost than $(b_i)$-- a contradiction. (end of proof)

Using this claim, we can greedily select the smallest $a_i$ for $i=1, \ldots, D$. If there are 0 test cases on day 0 and at least $b_i$ on day $m_i$, there must be a day $1 \le j \le m_i$ where $\lceil \frac{b_i}{m_i} \rceil$ test cases are prepared (max 1-day increase is at least average increase). $a_1$ is the maximum $a_i$, so $a_1$ must be at least $\max_{i=1}^D \lceil \frac{b_i}{m_i} \rceil$. Let $a_1 = \max_{i=1}^D \lceil \frac{b_i}{m_i} \rceil$ and decrement all $m_i$. If we set all $a_i$ in this manner, $(a_i)$ is

Therefore, this greedy algorithm (code below) attains the lex. min valid sequence, which we have shown is cost-optimal. Its time complexity is $O(D^3 + D^2 \log(B))$.

def ceildiv(a, b):
    return -(a // -b)

def solve(demands):
    MOD = 10**9 + 7
    ans = 0
    while len(demands) > 0:
        a1 = max(ceildiv(b, m) for m, b in demands)
        demands = [(m - 1, b - a1) for m, b in demands if b > a1]
        ans = (ans + pow(3, a1 - 1, MOD)) % MOD
    return ans

D = int(input())

demands = []
for _ in range(D):
    m, b = map(int, input().split())
    demands.append((m, b))

Subtask 2 ($D \leq 3000$):

Observation 2 implies that we only need to satisfy $(m_i, b_i)$ that are on the "upper left" hull of the demand set (where we assume $(0, 0)$ is also a demand). Let's take some $(a_1, a_2, \ldots)$ that satisfies everything on the upper left hull. We claim that we can "massage" the $a_i$ so that each $(m_i, b_i)$ on the upper left hull is exactly satisfied. We will also do this in a way so that if $(m_i, b_i)$, $(m_j, b_j)$ are consecutive on the hull, then $a_{m_i+1} \geq a_{i+2} \geq \cdots a_{m_j}$ still holds (so everything not on the hull is still automatically satisfied). To see how to do this, suppose $a_1 + a_2 + \cdots + a_{m_i} > b_i$ with $i$ minimal, and let $j > i$ be minimal such that $a_1 + a_2 + \cdots + a_{m_j} = b_j$ (also, $i, j$ are both on the hull). Then, we have $a_{m_{i-1}+1} + \cdots + a_{m_i} > b_i - b_{i-1}$, but $a_{m_{j-1}} + \cdots + a_{m_j} < b_j - b_{j-1}$. By convexity, we must have $\frac{b_i - b_{i-1}}{m_i - m_{i-1}} \geq \frac{b_j - b_{j-1}}{m_j - m_{j-1}}$, so we have $a_{m_{i-1}+1} > a_{m_j}$. We can then move $1$ test-case from the last $a_k = a_{m_{i-1}+1}$ (with $m_{i-1}+1\leq k \leq m_i$) to the first $a_\ell = a_{m_j}$ (with $m_{j-1}+1\leq \ell \leq m_j$). In this way, we have moved a subtask from a day with $a_k$ subtasks to a day with $a_\ell < a_k$ subtasks, which does not increase the total cost.

The point of this argument is as follows: Suppose $(0, 0), (m_{i_1}, b_{i_1}), \ldots, (m_{i_k}, b_{i_k})$ is the upper left hull. Then, we can assume Bessie has prepared exactly $b_{i_t}$ test-cases by day $m_{i_t}$. In particular, between days $m_{i_{t-1}+1}$ and $m_{i_t}$ (inclusive), Bessie prepares $b_{i_t} - b_{i_{t-1}}$ test cases. By convexity of $3^{a-1}$, we want the number of test cases per day to be as close together as possible, so we should have them all be either $\lceil x \rceil$ or $\lfloor x \rfloor$, $x$ being the average number of test cases prepared in this interval.

This gives us an $O(D^2(\log D + \log B))$ solution (code below).

#include <algorithm>
#include <iostream>
#include <stack>
typedef long long ll;
typedef std::pair<ll,ll> pi;
const int MAXN = 2e5+5;
const ll P = 1000000007;
int N;
pi p[MAXN];
ll modexp (ll a, ll n) {
	if (n == 0) return 1;
	ll b = modexp((a*a)%P, n/2);
	return (n%2?(a*b)%P:b);
void input () {
	std::cin >> N;
	for (int i = 0; i < N; i++) {
		std::cin >> p[i].first >> p[i].second;
bool pre (pi p, pi q) {
	// returns true if line to p is on or below line to q
	return p.second*q.first <= q.second*p.first;
ll diff (pi p, pi q) {
	ll dy = q.second - p.second;
	ll dx = q.first - p.first;
	ll nh = dy%dx%P;
	ll lo = dy/dx;
	if (lo == 0) {
		return ((nh%P) * modexp(3, lo))%P;
	return (modexp(3, lo-1)*((dx-nh)%P) + modexp(3, lo)*(nh%P))%P;
ll query (int M) {
	std::sort(p, p+M);
	std::stack<pi> stk;
	stk.push({0, 0});
	for (int i = 0; i < M; i++) {
		while (int(stk.size()) > 1) {
			pi q = stk.top();
			pi r = stk.top();
			if (pre({q.first-r.first, q.second-r.second}, {p[i].first-r.first, p[i].second-r.second})) {
			else {
		if (stk.top().second < p[i].second) {
	ll ans = 0;
	pi cur = stk.top();
	while (!stk.empty()) {
		ans = (ans + diff(stk.top(), cur))%P;
		cur = stk.top();
	return ans;
int main () {
	for (int i = 1; i <= N; i++) {
		std::cout << query(i) << "\n";

Subtask 3 ($D \leq 2\cdot 10^5$):

To optimize, we need to efficiently maintain consecutive pairs of points on the hull as points are added. For two sets of points $A$, $B$, $h(A \cup B)=h(h(A), h(B))$, where $h(S)$ denotes the convex hull of $S$, a set of 2d points. This means that a point that's not on the convex hull will never be after new points are added. Thus, inserting a new point inserts at most 1 new point to the hull and deletes possibly many.

We can maintain a set of $(x,y)$ points on the hull, sorted by $x$ (and $y$). Updating the convex hull after inserting a point $p$ could require removing a ball of points around $p$. Say $p$ has index $i$ in the sorted set. We can repeatedly check if $i \rightarrow (i+1) \rightarrow (i+2)$ forms a left turn; if so, $i+1$ does not belong on the hull. Similarly, check for right turns of the form $(i-2)\leftarrow(i-1)\leftarrow i$.

Note that $a_i$s should never be negative, so we should remove $i+1$ whenever $i\rightarrow(i+1)$ is downward sloping. Each point is removed at most once in $O(\log D)$ time, and exponentiating to calculate the costs involving it is $O(\log B)$ per hull edge. The total work is $O(D(\log D+\log B))$.


using namespace std;

typedef long long ll;

template <ll Mod>
struct ModInt {
  ll n;

  ModInt(const ll x = 0) : n(x) {
    while (n < 0) n += Mod;
    n %= Mod;
  explicit operator int() const { return n; }
  inline ModInt operator+(const ModInt r) const noexcept { return ModInt(*this) += r; }
  inline ModInt operator-(const ModInt r) const noexcept { return ModInt(*this) -= r; }
  inline ModInt operator*(const ModInt r) const noexcept { return ModInt(*this) *= r; }
  inline ModInt operator/(const ModInt r) const noexcept { return ModInt(*this) /= r; }
  inline ModInt &operator+=(const ModInt r) noexcept {
    n += r.n;
    if (n >= Mod) n -= Mod;
    return *this;
  inline ModInt &operator-=(const ModInt r) noexcept {
    if (n < r.n) n += Mod;
    n -= r.n;
    return *this;
  inline ModInt &operator*=(const ModInt r) noexcept {
    n = n * r.n % Mod;
    return *this;
  inline ModInt &operator/=(const ModInt r) noexcept { return *this *= r.inv(); }

  inline ModInt pow(ll x) const noexcept {
    ModInt<Mod> ret(1), tmp(*this);
    while (x) {
      if (x&1) ret *= tmp;
      tmp *= tmp;
      x >>= 1;
    return ret;
  inline ModInt inv() const noexcept { return pow(Mod-2); }

  friend ostream& operator<<(ostream& os, const ModInt& obj) { return os << obj.n; }
  friend istream& operator>>(istream& is, ModInt& obj) {
    ll t;
    is >> t;
    obj = ModInt(t);
    return is;

const ll mod = 1000000007;
using mi = ModInt<mod>;

int main(){

    int D; cin >> D;

    mi ans=0;

    map<int, ll> ys;
    set<int> xs({0});

    auto left_turn=[&](int x1, int x2, int x3)->bool{
        return (ys[x2]-ys[x1])*(x3-x2) <= (ys[x3]-ys[x2])*(x2-x1);

    auto right_turn=[&](int x1, int x2, int x3)->bool{
        return !left_turn(x1, x2, x3);

    auto f=[&](int x1, int x2)->mi{
        int dx = x2 - x1;
        ll dy = ys[x2] - ys[x1];
        if(dy<=0) return 0;
        // dx*k <= dy <= dx*(k+1)
        ll step = dy/dx;
        if(dy%dx) return mi(3).pow(dy/dx)*(dy%dx) + (dy/dx? mi(3).pow(dy/dx-1) : 0) *(dx-(dy%dx));
        return dy/dx? mi(3).pow(dy/dx-1)*dx : 0;

    auto upd=[&](int x, bool del = 0){
        auto it = xs.lower_bound(x);
        assert(*it == x);
        assert(it != xs.begin());
        int x_bef = *prev(it);
            ans -= f(x_bef, x);
            if(it != xs.end()){
                int x_af = *it;
                ans += f(x_bef, x_af) - f(x, x_af);
            ys[x] = 0;
        } else{
            ans += f(x_bef, x);
            if(it != xs.end()){
                int x_af = *it;
                ans += f(x, x_af) - f(x_bef, x_af);

    auto ins=[&](int x, ll y){
        // check if x -- y -- z y is below segment (x-z) in CH -- if so return
        if(ys[x] and ys[x] >= y) return;
        if(ys[x]) upd(x, 1);
        ys[x] = y;
            auto it = xs.lower_bound(x);
            bool ch = 0;
            for(int i=0; i<3; i++){
                if(it!=xs.end() and next(it)!=xs.end() and next(next(it))!=xs.end()){
                    int a=*it, b=*next(it), c=*next(next(it));
                    if(left_turn(a, b, c)){
                        ch = 1;
                        upd(b, 1);
                if(it==xs.begin()) break;
            if(!ch) break;

        int t;
        ll b;
        cin >> t >> b;
        ins(t, b);
        cout << ans << "\n";

Note that the solution is correct even if you divide when computing left_turn instead of multiply:

auto left_turn = [&](int x1, int x2, int x3) -> bool {
	return ys[x2] <= ys[x3] && (ys[x2] - ys[x1]) / (x2 - x1) <= (ys[x3] - ys[x2]) / (x3 - x2);