Submission #882002

#	Time	Username	Problem	Language	Result	Execution time	Memory
882002		alexdd	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	505 ms	31660 KiB

route

#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;
        }
        bool eq=1;
        for(int i=1;i<=n;i++)
        {
            if(root[i]!=root[1])
            {
                eq=0;
                break;
            }
        }
        if(eq)
            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

*/

• Subtask 1: 100 / 100