Codeforces460C【二分+线段树】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=1e5+10;
struct SegT{
    int sum;
    int val;
    int left;
    int right;
};

SegT q[N*4];
char id[N];
int n,m,w;
int a[N];

void Build(int num,int L ,int R)
{
    q[num].left=L;
    q[num].right=R;
    q[num].val=0;
    if(L==R)
    {
        q[num].sum=a[L];
        return;
    }
    int mid=(L+R)>>1;
    Build(2*num,L,mid);
    Build(2*num+1,mid+1,R);
    q[num].sum=q[2*num].sum+q[2*num+1].sum;
}

void PushDown(int num)
{
    if(q[num].val)
    {
        q[2*num].sum+=(q[2*num].right - q[2*num].left+1)*q[num].val;
        q[2*num].val+=q[num].val;
        q[2*num+1].sum+=(q[2*num+1].right - q[2*num+1].left+1)*q[num].val;
        q[2*num+1].val+=q[num].val;
        q[num].val=0;
    }
}

void Update(int num,int s,int t,int v)
{
    if(q[num].left>=s&&q[num].right<=t)
    {
        q[num].sum+=(q[num].right - q[num].left+1)*v;
        q[num].val+=v;
        return;
    }
    PushDown(num);
    int mid=(q[num].left+q[num].right)>>1;
    if(mid>=t)
        Update(2*num,s,t,v);
    else if(mid<s)
        Update(2*num+1,s,t,v);
    else
    {
        Update(2*num,s,mid,v);
        Update(2*num+1,mid+1,t,v);
    }
    q[num].sum=q[2*num].sum+q[2*num+1].sum;
}

int query(int num,int x)
{
    if(q[num].left==q[num].right&&q[num].left==x)
        return q[num].sum;
    PushDown(num);

    int mid=(q[num].left+q[num].right)>>1;

    if(mid>=x)
        return query(2*num,x);
    else
        return query(2*num+1,x);
}

bool Judge(int k)
{
    int ti=0;
    int tmp,x;
    Build(1,1,n);
    for(int i=n;i>=1;i--)
    {
        tmp=query(1,i);
        if(tmp>=k) continue;
        x=k-tmp;
        if(i>=w)
        {
            Update(1,i-w+1,i,x);
            ti+=x;
        }
        else
        {
            Update(1,1,i,x);
            ti+=x;
        }
        if(ti>m) return false;
    }
    return true;
}

int main()
{
    scanf("%d%d%d",&n,&m,&w);
    int tmax=1,tmin=2e9;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tmax=max(tmax,a[i]);
        tmin=min(tmin,a[i]);
    }
    int Left=tmin,Right=tmax+m;
    while(Left<Right)
    {
        int mid=Left+(Right-Left+1)/2;
        if(Judge(mid))
            Left=mid;
        else
            Right=mid-1;
    }
    printf("%dn",Left);
    return 0;
}