#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int a[1000005];
int root[1000005];
int tole[1000005];
int tori[1000005];
int lun(int x)
{
if(tole[x]<=tori[x])
return tori[x]-tole[x]+1;
else
return (n-tole[x]+1) + tori[x];
}
priority_queue<pair<int,int>> pq;
void initializeaza_secvente()
{
if(a[1]==a[n])
{
for(int i=1;i<=n;i++)
{
if(a[i]!=a[1])
break;
root[i]=1;
tori[1]=i;
}
for(int i=n;i>0;i--)
{
if(a[i]!=a[n])
break;
root[i]=1;
tole[1]=i;
}
int aux = tori[1]+1;
root[aux] = aux;
tole[aux] = aux;
for(int i=tori[1]+2;i<tole[1];i++)
{
if(a[i]!=a[i-1])
{
tori[aux]=i-1;
aux=i;
tole[i]=i;
}
root[i]=aux;
}
tori[aux]=tole[1]-1;
}
else
{
int aux=1;
root[1]=1;
tole[1]=1;
for(int i=2;i<=n;i++)
{
if(a[i]!=a[i-1])
{
tori[aux]=i-1;
aux=i;
tole[i]=i;
}
root[i]=aux;
}
tori[aux]=n;
}
for(int i=1;i<=n;i++)
{
if(root[i]==i)
{
int tol = tole[i]-1;
if(tol==0)
tol=n;
int tor = tori[i]+1;
if(tor==n+1)
tor=1;
if(a[tol]>a[i] && a[tor]>a[i])
{
pq.push({-lun(i),i});
}
}
}
//for(int i=1;i<=n;i++)
// cout<<root[i]<<" ";
}
void unite(int x, int y)
{
if(lun(x) <= lun(y))
{
tole[y] = tole[x];
int j = tole[x];
while(j!=tori[x])
{
root[j] = y;
j++;
if(j==n+1)
j=0;
}
root[tori[x]] = y;
}
else
{
tori[x] = tori[y];
int j = tole[y];
while(j!=tori[y])
{
root[j] = x;
j++;
if(j==n+1)
j=0;
}
root[tori[y]] = x;
}
}
int solve_greedy()
{
bool bl=1;
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=a[1])
bl=0;
if(i>1) sum += abs(a[i]-a[i-1]);
}
sum += abs(a[1]-a[n]);
if(bl)
{
return 0;
//cout<<0;
//return 0;
}
initializeaza_secvente();
while(!pq.empty())
{
int x = pq.top().second;
pq.pop();
//cout<<x<<" zzz\n";
if(lun(x) > k)
break;
int tol = tole[x]-1;
if(tol==0)
tol=n;
int tor = tori[x]+1;
if(tor==n+1)
tor=1;
if(lun(x) * (min(a[root[tol]],a[root[tor]]) - a[x]) < k)
{
if(a[root[tol]]<a[root[tor]])
{
k -= lun(x) * (a[root[tol]] - a[x]);
a[x] = a[root[tol]];
unite(root[tol], x);
}
else if(a[root[tol]]>a[root[tor]])
{
k -= lun(x) * (a[root[tor]] - a[x]);
a[x] = a[root[tor]];
unite(x, root[tor]);
}
else
{
k -= lun(x) * (a[root[tor]] - a[x]);
a[x] = a[root[tor]];
unite(root[tol], x);
unite(root[x], root[tor]);
}
}
else
{
a[x] += k / lun(x);
break;
}
if(lun(root[1])==n)
break;
///trebuie sa verificam daca tot sirul ii egal, atunci dam break
x = root[x];
tol = tole[x]-1;
if(tol==0)
tol=n;
tor = tori[x]+1;
if(tor==n+1)
tor=1;
if(a[tol] > a[x] && a[tor] > a[x])
{
pq.push({-lun(x),x});
}
}
for(int i=1;i<n;i++)
{
sum -= abs(a[root[i+1]] - a[root[i]]);
}
sum -= abs(a[root[n]] - a[root[1]]);
return sum;
}
signed main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
cout<<solve_greedy();
return 0;
}
/**
9 1000
1 1 1 2 2 3 3 1 1
9 1000
1 1 1 3 3 3 3 1 1
10 1000
5 4 3 2 1 1 2 3 4 5
8 3
7 9 1 1 9 9 9 9
n = 2 ?????
3 3
4 8 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
25 ms |
10844 KB |
Output is correct |
| 11 |
Correct |
30 ms |
11828 KB |
Output is correct |
| 12 |
Correct |
26 ms |
10580 KB |
Output is correct |
| 13 |
Correct |
287 ms |
31656 KB |
Output is correct |
| 14 |
Correct |
276 ms |
31480 KB |
Output is correct |
| 15 |
Correct |
229 ms |
31668 KB |
Output is correct |
| 16 |
Correct |
248 ms |
31624 KB |
Output is correct |
| 17 |
Correct |
264 ms |
31660 KB |
Output is correct |
| 18 |
Correct |
268 ms |
31668 KB |
Output is correct |
| 19 |
Correct |
288 ms |
31668 KB |
Output is correct |
| 20 |
Correct |
198 ms |
27320 KB |
Output is correct |
