Submission

Score: 0

User: yourmom

Problemset: ความลึก

Language: cpp

Time: 0.032 second

Submitted On: 2026-10-03 15:13:29

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

struct DSU {
    vector<int> p, r;
    vector<long long> sz;
    DSU(int n) {
        p.resize(n);
        r.assign(n, 0);
        sz.assign(n, 0);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    void unite(int a, int b, long long& curmax) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        if (r[a] == r[b]) r[a]++;
        curmax = max(curmax, sz[a]);
    }
};

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

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

    vector<pair<int, long long>> segs(N); // {depth, length}
    int cur = 1, maxd = 1;
    for (int i = 0; i < N; i++) {
        int D, L;
        cin >> D >> L;
        cur += D;
        segs[i] = {cur, L};
        maxd = max(maxd, cur);
    }

    // เรียงตาม depth จากมากไปน้อย
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return segs[a].first > segs[b].first;
    });

    vector<long long> maxw(maxd + 1, 0);
    DSU dsu(N);
    vector<char> active(N, 0);
    long long curmax = 0;
    int j = 0;

    for (int h = maxd; h >= 1; h--) {
        while (j < N && segs[order[j]].first >= h) {
            int i = order[j++];
            active[i] = 1;
            dsu.sz[i] = segs[i].second;
            curmax = max(curmax, dsu.sz[i]);

            if (i > 0 && active[i - 1]) dsu.unite(i, i - 1, curmax);
            if (i + 1 < N && active[i + 1]) dsu.unite(i, i + 1, curmax);
        }
        maxw[h] = curmax;
    }

    // ตอบคำถาม
    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;
}