Overview

There are \(N\) streetlights that gradually become dark over time. For each query, given a time \(T_j\), we need to find the total number of pairs \((l, r)\) such that all streetlights in the contiguous interval are dark.

Analysis

1. Counting Dark Intervals

When \(m\) consecutive streetlights are all “dark,” the number of subintervals \((l, r)\) that can be chosen from them is \(\frac{m(m+1)}{2}\). If there are several maximal (non-extendable) contiguous dark intervals among all the streetlights, the total answer is \(\sum \frac{m_k(m_k+1)}{2}\) for each interval length \(m_k\).

2. State Changes and Monotonicity

The condition for streetlight \(i\) to be dark after \(t\) days is \(A_i - D_i \times t \le K\). Rearranging this expression, the minimum number of days \(S_i\) for streetlight \(i\) to become dark is as follows: - If \(A_i \le K\): it is dark from the start (\(S_i = 0\)) - If \(A_i > K\) and \(D_i > 0\): since \(t \ge \frac{A_i - K}{D_i}\), we have \(S_i = \lceil \frac{A_i - K}{D_i} \rceil\) - If \(A_i > K\) and \(D_i = 0\): it never becomes dark (\(S_i = \infty\))

Once a streetlight becomes dark, it stays dark forever. In other words, the number of “dark streetlights” only increases over time and never decreases.

3. Offline Processing of Queries

Checking all streetlights for each query would take \(O(NQ)\), which is too slow. However, by sorting the times \(S_i\) when streetlights become dark and the query times \(T_j\) in advance, we can perform offline processing where we add “newly darkened streetlights” to a set in chronological order.

Algorithm

1. Preparation:

   • Compute the time \(S_i\) at which each streetlight becomes dark.
   • Sort the streetlights in ascending order of \(S_i\).
   • Sort the queries in ascending order of \(T_j\) (we need to record the original order).

2. Data Structure:

   • Use a Disjoint Set Union (Union-Find / DSU) data structure to manage adjacent dark streetlights by connecting them.
   • Maintain the size (number of streetlights) \(m\) of each connected component.

3. Query Processing:

   • Sequentially process streetlights that have newly become dark up to the current time \(T_j\).
   • When streetlight \(i\) becomes dark:
     • Initially, an interval of length \(1\) is created, so add \(\frac{1(1+1)}{2} = 1\) to the running total.
     • If a neighbor (\(i-1\) or \(i+1\)) is already dark, merge with that component.
     • When merging, subtract the “pre-merge contribution \(\frac{m(m+1)}{2}\) of each component” from the total and add the “post-merge contribution of the new component,” performing an incremental update.

4. Output:

   • After processing all queries, output the results in the original query order.

Complexity

• Time Complexity: \(O((N + Q) \log (N + Q))\)
  • \(O(N)\) for computing \(S_i\)
  • \(O(N \log N + Q \log Q)\) for sorting streetlights and queries
  • \(O((N + Q) \alpha(N))\) for Union-Find operations (\(\alpha\) is the inverse Ackermann function)
• Space Complexity: \(O(N + Q)\)
  • For storing streetlight information, query information, Union-Find arrays, etc.

Implementation Notes

• Ceiling Division: \(S_i = \lceil \frac{A_i - K}{D_i} \rceil\) can be written in integer arithmetic as (A_i - K + D_i - 1) / D_i.

• Large Values: When \(D_i = 0\) and the streetlight never becomes dark, set \(S_i\) to a value sufficiently larger than the maximum query value (\(10^9\)).

• Incremental Updates: When merging connected components, instead of recomputing the entire sum each time, efficiently calculate by only adding and subtracting the parts that changed.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

/**
 * Problem: Dark Streetlight Intervals
 * We are given N streetlights, each with an initial brightness A_i and a decay rate D_i.
 * A light is "dark" if its brightness C_i(t) = max(0, A_i - D_i * t) is <= K.
 * For each query T_j, we need to count the number of pairs (l, r) such that all
 * streetlights from l to r are dark at time T_j.
 *
 * Solution Approach:
 * 1. For each light, calculate the earliest time S_i at which it becomes dark.
 *    - If A_i <= K, S_i = 0.
 *    - If A_i > K and D_i > 0, S_i = ceil((A_i - K) / D_i).
 *    - If A_i > K and D_i = 0, the light never becomes dark (S_i = infinity).
 * 2. Sort the lights by their activation time S_i and the queries by their time T_j.
 * 3. Use a Disjoint Set Union (DSU) to maintain continuous segments of dark lights.
 * 4. As time progresses (iterating through sorted queries), activate lights that have
 *    become dark and update the total count of dark sub-intervals.
 *    A segment of length m contributes m*(m+1)/2 sub-intervals.
 */

typedef long long ll;

// Disjoint Set Union (DSU) to maintain connected components of dark streetlights.
struct DSU {
    vector<int> parent;
    vector<ll> sz;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(n + 1, 0);
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // Union by size for efficiency
            if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
        }
    }
};

// Function to calculate the number of pairs (l, r) in a segment of length m.
inline ll f(ll m) {
    return m * (m + 1) / 2;
}

struct Light {
    int id;
    ll s;
};

struct Query {
    int id;
    ll t;
};

int main() {
    // Fast I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    ll K;
    if (!(cin >> N >> Q >> K)) return 0;

    // Calculate activation time for each streetlight
    vector<Light> lights(N);
    for (int i = 0; i < N; ++i) {
        ll a, d;
        cin >> a >> d;
        ll s;
        if (a <= K) {
            s = 0;
        } else if (d == 0) {
            // Light never becomes dark if it starts bright and doesn't decay
            s = 2000000007LL; 
        } else {
            // Activation time is ceil((A_i - K) / D_i)
            s = (a - K + d - 1) / d;
        }
        lights[i] = {i + 1, s};
    }

    // Store queries and their original indices
    vector<Query> queries(Q);
    for (int i = 0; i < Q; ++i) {
        queries[i].id = i;
        cin >> queries[i].t;
    }

    // Sort lights and queries by time
    sort(lights.begin(), lights.end(), [](const Light& a, const Light& b) {
        if (a.s != b.s) return a.s < b.s;
        return a.id < b.id;
    });
    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.t < b.t;
    });

    DSU dsu(N);
    vector<bool> is_dark(N + 2, false); // Padding to avoid boundary checks
    vector<ll> results(Q);
    ll total_count = 0;
    int light_idx = 0;

    // Process queries in chronological order
    for (int i = 0; i < Q; ++i) {
        while (light_idx < N && lights[light_idx].s <= queries[i].t) {
            int curr = lights[light_idx].id;
            if (!is_dark[curr]) {
                is_dark[curr] = true;
                dsu.sz[curr] = 1;
                total_count += f(1);

                // Merge with left neighbor if it is already dark
                if (curr > 1 && is_dark[curr - 1]) {
                    int root_left = dsu.find(curr - 1);
                    int root_curr = dsu.find(curr);
                    total_count -= f(dsu.sz[root_left]);
                    total_count -= f(dsu.sz[root_curr]);
                    dsu.unite(root_left, root_curr);
                    total_count += f(dsu.sz[dsu.find(curr)]);
                }
                // Merge with right neighbor if it is already dark
                if (curr < N && is_dark[curr + 1]) {
                    int root_right = dsu.find(curr + 1);
                    int root_curr = dsu.find(curr);
                    total_count -= f(dsu.sz[root_right]);
                    total_count -= f(dsu.sz[root_curr]);
                    dsu.unite(root_right, root_curr);
                    total_count += f(dsu.sz[dsu.find(curr)]);
                }
            }
            light_idx++;
        }
        results[queries[i].id] = total_count;
    }

    // Print results for each query in original order
    for (int i = 0; i < Q; ++i) {
        cout << results[i] << "\n";
    }

    return 0;
}

This editorial was generated by gemini-3-flash-thinking.