Submission #882006

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
882006	2023-12-02T11:53:32 Z	alexdd	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	292 ms	16040 KB

route

#include<bits/stdc++.h>
using namespace std;
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;
    }
}
long long solve_greedy()
{
    bool bl=1;
    long long 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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 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	6492 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6744 KB	Output is correct
10	Correct	33 ms	10684 KB	Output is correct
11	Correct	34 ms	9736 KB	Output is correct
12	Correct	27 ms	8788 KB	Output is correct
13	Correct	283 ms	15852 KB	Output is correct
14	Correct	292 ms	15956 KB	Output is correct
15	Correct	243 ms	15956 KB	Output is correct
16	Correct	262 ms	16040 KB	Output is correct
17	Correct	280 ms	16036 KB	Output is correct
18	Correct	284 ms	15956 KB	Output is correct
19	Correct	280 ms	15952 KB	Output is correct
20	Correct	204 ms	15808 KB	Output is correct