#include<iostream>
#include<queue>
using namespace std;
#define int long long
int n,k;
int a[1000005];
int root[1000005];
int tole[1000005];
int tori[1000005];
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;
}
pq.push({-(tori[1]-tole[1]),1});
int aux = tori[1]+1;
root[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({-(a[tori[i]]-a[tole[i]]),i});
}
}
}
//for(int i=1;i<=n;i++)
// cout<<root[i]<<" ";
}
void unite(int x, int y)
{
if(tori[x]-tole[x] <= tori[y]-tole[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[x]] = x;
}
}
signed main()
{
cin>>n>>k;
bool bl=1;
int sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[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)
{
cout<<0;
return 0;
}
initializeaza_secvente();
/*for(int i=1;i<=n;i++)
{
if(i==1 || root[i]!=root[i-1])
{
cout<<root[i]<<" "<<tole[root[i]]<<" "<<tori[root[i]]<<" "<<a[root[i]]<<"\n";
}
}*/
while(!pq.empty())
{
int x = pq.top().second;
pq.pop();
//cout<<x<<" zzz\n";
if(tori[x]-tole[x]+1 > k)
break;
int tol = tole[x]-1;
if(tol==0)
tol=n;
int tor = tori[x]+1;
if(tor==n+1)
tor=1;
if((tori[x]-tole[x]+1) * (min(a[root[tol]],a[root[tor]]) - a[x]) < k)
{
if(a[root[tol]]<a[root[tor]])
{
k -= (tori[x]-tole[x]+1) * (a[root[tol]] - a[x]);
a[x] = a[root[tol]];
unite(root[tol], x);
}
else if(a[root[tol]]>a[root[tor]])
{
k -= (tori[x]-tole[x]+1) * (a[root[tor]] - a[x]);
a[x] = a[root[tor]];
unite(x, root[tor]);
}
else
{
k -= (tori[x]-tole[x]+1) * (a[root[tor]] - a[x]);
a[x] = a[root[tor]];
unite(root[tol], x);
unite(root[x], root[tor]);
}
}
else
{
a[x] += k / (tori[x]-tole[x]+1);
break;
}
/*for(int i=1;i<=n;i++)
cout<<a[root[i]]<<" ";
cout<<"\n";
for(int i=1;i<=n;i++)
{
if(i==1 || root[i]!=root[i-1])
{
cout<<root[i]<<" "<<tole[root[i]]<<" "<<tori[root[i]]<<" "<<a[root[i]]<<"\n";
}
}*/
bool eq=1;
for(int i=1;i<=n;i++)
{
if(root[i]!=root[1])
{
eq=0;
break;
}
}
if(eq)
{
//cout<<"oh no equal\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({-(tori[x]-tole[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]]);
cout<<sum;
return 0;
}
/**
9 1000
1 1 1 2 2 3 3 1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
4540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
