Submission

Score: 100

User: yourmom

Problemset: ความลึก

Language: cpp

Time: 0.030 second

Submitted On: 2026-10-03 15:20:11

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

struct DSU {
    vector<int> p;
    vector<long long> sz;

    DSU(int n) : p(n), sz(n, 0) {
        iota(p.begin(), p.end(), 0);
    }

    int find(int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }

    void activate(int x, long long len) {
        p[x] = x;
        sz[x] = len;
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

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 = 0, maxDepth = 0;

    for (int i = 0; i < N; ++i) {
        int D;
        cin >> D >> len[i];

        cur += D;
        depth[i] = cur;
        maxDepth = max(maxDepth, cur);
    }

    // nodes[d] = ช่วงที่มีความลึก d
    vector<vector<int>> nodes(maxDepth + 1);
    for (int i = 0; i < N; ++i)
        nodes[depth[i]].push_back(i);

    DSU dsu(N);
    vector<char> active(N, false);

    // best[d] = ความยาวต่อเนื่องสูงสุดที่ทุกจุดมี depth >= d
    vector<long long> best(maxDepth + 1, 0);

    long long currentBest = 0;

    for (int d = maxDepth; d >= 1; --d) {
        for (int i : nodes[d]) {
            active[i] = true;
            dsu.activate(i, len[i]);

            if (i > 0 && active[i - 1])
                dsu.unite(i, i - 1);

            if (i + 1 < N && active[i + 1])
                dsu.unite(i, i + 1);
        }

        // หา maximum component
        for (int i : nodes[d]) {
            currentBest = max(currentBest, dsu.sz[dsu.find(i)]);
        }

        best[d] = currentBest;
    }

    while (Q--) {
        long long W;
        cin >> W;

        int lo = 1, hi = maxDepth, ans = 0;

        while (lo <= hi) {
            int mid = (lo + hi) / 2;

            if (best[mid] >= W) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        cout << ans << '\n';
    }

    return 0;
}