Submission #881975

#	Time	Username	Problem	Language	Result	Execution time	Memory
881975		alexdd	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	2 ms	6744 KiB

route

#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;
        }
        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({-(tori[i]-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[y]] = x;
    }
}
void verif_debug()
{

}
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())
    {
        verif_debug();
        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

9 1000
1 1 1 3 3 3 3 1 1

10 1000
5 4 3 2 1 1 2 3 4 5

8 2
9 9 9 9 1 9 9 9

*/

• Subtask 1: 0 / 100