Submission

Score: 100

User: qweqwe

Problemset: ความลึก

Language: cpp

Time: 0.025 second

Submitted On: 2026-02-25 20:01:36

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;

int main(){
	fastio;
	int n,m;
	cin >> n >> m;
	
	vector<ll> maxAllDepth(n,0),curAllDepth(n,0);
	maxAllDepth[0] = LLONG_MAX;
	ll curDepth = 0, maxDepth = 0;
	
	for (int i=0;i<n;i++){
		int depth,length;
		cin >> depth >> length;
		
		curDepth+=depth;
		curAllDepth[curDepth]+=length;
		
		if (curDepth < maxDepth){
			maxAllDepth[maxDepth] = max(maxAllDepth[maxDepth],
										curAllDepth[maxDepth]);
			
			curAllDepth[curDepth] += curAllDepth[maxDepth];
			curAllDepth[maxDepth] = 0;
			maxDepth = curDepth;
		}
		//cout << curDepth << " " << maxDepth << "\n";
		maxDepth = max(maxDepth,curDepth);
	}
	for (int i=0;i<n;i++){
		if (curAllDepth[i] != 0){
			maxAllDepth[i] = max(maxAllDepth[i],
								curAllDepth[i]);
		}
	}
	/*
	for (int i=0;i<n;i++){
		cout << maxAllDepth[i] << "\n";
	}cout << "\n";
	*/
	for (int i=0;i<m;i++){
		ll boatWidth;
		cin >> boatWidth;
		ll pos =upper_bound(maxAllDepth.begin(),maxAllDepth.end(),boatWidth,greater<ll>()) - maxAllDepth.begin();
		cout << pos - 1 << "\n";
	}
	return 0;
}