Submission

-P-P------

Score: 20

User: hmmm

Problemset: ความลึก

Language: cpp

Time: 0.039 second

Submitted On: 2025-04-05 14:38:51

#include<bits/stdc++.h>
using namespace std;
using pii=array<int,2>;
const int N=1e5+5;
vector<pii> p;
int l[N],r[N],ans[N];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m,sum=0,cnt=0;
    cin >> n >> m;
    p.push_back({0,0});
    for(int i=1;i<=n;i++){
        int x,y;
        cin >> x >> y;
        sum+=x;
        cnt+=y;
        p.push_back({sum,cnt});
    }
    p.push_back({0,cnt});
    stack<int> st;
    st.push(0);
    for(int i=1;i<=n;i++){
        while(st.top()>0 && p[st.top()][0]>=p[i][0]){
            st.pop();
        }
        l[i]=st.top();
        st.push(i);
    }
    while(!st.empty()) st.pop();
    st.push(n+1);
    for(int i=n;i>0;i--){
        while(st.top()<n+1 && p[st.top()][0]>=p[i][0]){
            st.pop();
        }
			r[i]=st.top();
      st.push(i);        
    }
    while(!st.empty()) st.pop();
    
    for(int i=1;i<=n;i++){
        // cout << ans[i] << ' ';
        // cout << p[i][0] << " ";
        // cout << p[l[i]][1] << ' ' << p[r[i]][1] << "\n";
      	ans[p[i][0]]=max(ans[p[i][0]],abs(p[l[i]][1]-p[r[i]][1]+1));
      
    }
    vector<int> dis;
    int id=n;
    while(ans[id]==0) id--;
  	for(int i=id;i>=1;i--){
        dis.push_back(ans[i]);
        // cout << ans[i] << ' ';
    }
    while(m--){
        int x;
        cin >> x;
        auto v=lower_bound(dis.begin(),dis.end(),x)-dis.begin();
        cout << id-v << "\n";
    }
}