Submission

Score: 0

User: yourmom

Problemset: ความลึก

Language: cpp

Time: 0.029 second

Submitted On: 2026-10-03 15:09:59

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<int> depth(N);
    vector<long long> len(N);
    int cur = 1, maxd = 1;

    for (int i = 0; i < N; i++) {
        int D, L;
        cin >> D >> L;
        cur += D;
        depth[i] = cur;
        len[i] = L;
        maxd = max(maxd, cur);
    }

    // maxw[h] = ความยาวต่อเนื่องยาวสุดที่ depth >= h
    vector<long long> maxw(maxd + 2, 0);

    // ใช้ stack หาช่วงที่ใหญ่ที่สุดที่ depth[i] เป็นค่าต่ำสุด
    vector<int> L(N), R(N);          // ขอบซ้าย-ขวา
    vector<long long> sum(N + 1, 0);  // prefix sum ของความยาว
    for (int i = 0; i < N; i++) sum[i + 1] = sum[i] + len[i];

    // หาขอบซ้าย
    stack<int> st;
    for (int i = 0; i < N; i++) {
        while (!st.empty() && depth[st.top()] >= depth[i]) st.pop();
        L[i] = st.empty() ? 0 : st.top() + 1;
        st.push(i);
    }

    // หาขอบขวา
    while (!st.empty()) st.pop();
    for (int i = N - 1; i >= 0; i--) {
        while (!st.empty() && depth[st.top()] >= depth[i]) st.pop();
        R[i] = st.empty() ? N - 1 : st.top() - 1;
        st.push(i);
    }

    // อัปเดต maxw
    for (int i = 0; i < N; i++) {
        long long width = sum[R[i] + 1] - sum[L[i]];
        maxw[depth[i]] = max(maxw[depth[i]], width);
    }

    // แพร่ค่าจากสูงลงต่ำ
    for (int h = maxd - 1; h >= 1; h--) {
        maxw[h] = max(maxw[h], maxw[h + 1]);
    }

    // ตอบคำถาม
    while (Q--) {
        long long W;
        cin >> W;
        int lo = 0, hi = maxd;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (maxw[mid] >= W) lo = mid;
            else hi = mid - 1;
        }
        cout << lo << '\n';
    }
    return 0;
}