답안 #882006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
882006 2023-12-02T11:53:32 Z alexdd 등산 경로 (IZhO12_route) C++17
100 / 100
292 ms 16040 KB
#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;
}
# 결과 실행 시간 메모리 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