cjb-poi2010blocks

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n,m;
int a[1100000];
long long pre[1100000];
int query(int k)
{
    rep(i,n)a[i]-=k;
    rep(i,n)pre[i]=pre[i-1]+a[i];
    static stack<int> q;
    while (!q.empty())q.pop();
    for(int i=0;i<=n;i++)if (q.empty() || pre[i]<pre[q.top()])q.push(i);
    int ans=0;
    for(int i=n;i>=1;i--)
    {
        while (!q.empty() && q.top()>i)q.pop();
        while (!q.empty() && pre[q.top()]<=pre[i])
            ans=max(ans,i-q.top()),q.pop();
    }
    rep(i,n)a[i]+=k;
    return ans;
}
int main()
{
    cin>>n>>m;
    rep(i,n)scanf("%d",&a[i]);
    rep(i,m){ int k; scanf("%d",&k); printf("%d%c",query(k),i==m?'\n':' '); }
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n,m;
int a[1100000];
long long pre[1100000];
int query(int k)
{
    rep(i,n)a[i]-=k;
    rep(i,n)pre[i]=pre[i-1]+a[i];
    static stack<int> q;
    while (!q.empty())q.pop();
    for(int i=0;i<=n;i++)if (q.empty() || pre[i]<pre[q.top()])q.push(i);
    int ans=0;
    for(int i=n;i>=1;i--)
    {
        while (!q.empty() && q.top()>i)q.pop();
        while (!q.empty() && pre[q.top()]<=pre[i])
            ans=max(ans,i-q.top()),q.pop();
    }
    rep(i,n)a[i]+=k;
    return ans;
}
int main()
{
    cin>>n>>m;
    rep(i,n)scanf("%d",&a[i]);
    rep(i,m){ int k; scanf("%d",&k); printf("%d%c",query(k),i==m?'\n':' '); }
    return 0;
}