Submission

PPPPPPPPPP

Score: 100

User: Ecir

Problemset: ความลึก

Language: cpp

Time: 0.030 second

Submitted On: 2025-03-23 14:54:46

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
#define twod array<ll,2>
#define thrd array<ll,3>
vector<twod> arr;
int mn[2][100009];
ll dis[100009];
vector<int> dep;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,nn;cin >> n >> nn;
    int sum=0;
    int l=0;
  int mx=0;
    arr.push_back({0,0});
    for(int i=1;i<=n;i++){
    int u,w;cin >> u >> w;
  	if(u>0){
      sum++;
      l+=w;
      arr.push_back({sum,l});
    }
    else{
      sum--;
      l+=w;
      arr.push_back({sum,l});
    }
      mx=max(mx,sum);
  }
 arr.push_back({0,l});
  // for(auto e:arr) cout << e[0] << "," << e[1] << ' ';
  // cout << "\n";
  stack<int> st;
  st.push(0);
  for(int i=1;i<=arr.size();i++){
    while(st.top()>0 && arr[st.top()-1][0]>=arr[i-1][0]) st.pop();
    mn[0][i]=st.top();
    st.push(i);
  }
  while(!st.empty()) st.pop();
  st.push(arr.size()+1);
  for(int i=arr.size();i>=1;i--){
  	while(st.top()<arr.size()+1 && arr[st.top()-1][0]>=arr[i-1][0]) st.pop();
    mn[1][i]=st.top();
    st.push(i);
  }
  for(int i=1;i<=arr.size();i++){
  	dis[arr[i-1][0]]=max(dis[arr[i-1][0]],abs(arr[mn[0][i]-1][1]-arr[mn[1][i]-2][1]));
  }
  for(int i=mx;i>=1;i--) dep.push_back(dis[i]);
  // for(int i=1;i<=4;i++) cout << dis[i] << "\n";
  // reverse(dep.begin(),dep.end());
  // 19 15 5 3
  while(nn--){
    int z;cin >> z;
    int pos=lower_bound(dep.begin(),dep.end(),z)-dep.begin();
    if(pos==dep.size()) cout << 0 << "\n";
    else cout << dep.size()-pos << "\n";
  }
  
  return 0;
}