4385: [POI2015]Wilcze doły (단조 로 운 대기 열)

http://www.lydsy.com/JudgeOnline/problem.php?id=4385
Description
길이 가 n 인 시퀀스 를 지정 합 니 다. 연속 길이 가 d 를 초과 하지 않 는 구간 을 선택 하여 안의 모든 숫자 를 0 으로 변경 할 수 있 습 니 다.이 구간 의 모든 숫자의 합 이 p 를 초과 하지 않도록 가장 긴 연속 구간 을 찾 으 십시오.
Input
첫 번 째 줄 은 세 개의 정수 n, p, d (1 < = d < = n < = n < = 200000, 0 < = p < = 10 ^ 16) 를 포함한다.두 번 째 줄 은 n 개의 정 수 를 포함 하고 순서대로 배열 의 모든 수 와 이 를 나타 낸다.
Output
수정 후 찾 을 수 있 는 가장 긴 조건 에 맞 는 구간 의 길 이 를 포함 합 니 다.
Sample Input
9 7 2
3 4 1 9 4 1 7 1 3 Sample Output
5
접두사 와 f [i] 와 s [i] 를 유지 합 니 다. s [i] 는 i 부터 길이 가 d 인 구간 의 합 을 표시 합 니 다.그리고 단조 로 운 대기 열 이 한 구간 을 유지 하여 이 구간 을 만족 시 킵 니 다: f [j] - f [i] - MAX [s [x]]
단조 로 운 대기 열 은 s [x] 의 최대 값 을 유지 합 니 다.그리고 구간 상황 에 따라 왼쪽 점 을 움 직 여...
% lld 회 AC.I64d 회 WA.

#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int N = 2*1e6 + 100;
LL f[N],que[N],s[N];
int pos[N];
int main()
{
        int n,d;
        LL x,p;
        scanf("%d%lld%d",&n,&p,&d);
        for(int i=1;i<=n;i++) scanf("%lld",&x), f[i] = f[i-1] + x;
        for(int i=1;i<=n-d+1;i++) s[i] = f[i+d-1] - f[i-1];        

        int head = 1, tail = 0, l = 0;
        int ans = d;
        for(int i=d , j = 1; i<=n; i++, j++)
        {
                while( head <=tail && que[tail]<=s[j] ) tail--;
                que[++tail] = s[j];
                pos[tail] = j;

                while( l p )
                {
                        l++;
                        if( l >= pos[head] ) head++;
                }
                ans = max( ans, i - l );
        }
        printf("%d
",ans);
        return 0;
}