Submission

Score: 0

User: yourmom

Problemset: รถขนส่ง

Language: cpp

Time: 0.100 second

Submitted On: 2026-10-03 15:03:35

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

struct UF {
    vector<int> p, r;
    vector<long long> sz;
    UF(int n = 0) { init(n); }
    void init(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;
    if (!(cin >> N >> Q)) return 0;
    
    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);
    }
    
    // maxw[h] = max contiguous length with depth >= h
    vector<long long> maxw(maxd + 1, 0);
    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;
    });
    
    UF uf(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;
            uf.sz[i] = segs[i].second;
            curmax = max(curmax, uf.sz[i]);
            if (i > 0 && active[i - 1]) uf.unite(i, i - 1, curmax);
            if (i + 1 < N && active[i + 1]) uf.unite(i, i + 1, curmax);
        }
        maxw[h] = curmax;
    }
    
    // answer queries
    while (Q--) {
        long long W;
        cin >> W;
        // binary search largest h with maxw[h] >= 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;
}