Submission #1119987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119987		Tenis0206	Text editor (CEOI24_editor)	C++11	56 / 100	1803 ms	982420 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int oo = LLONG_MAX;
const int nmax = 1e6;

int n;
int l[nmax + 5];

int sl, sc, el, ec;

int *d[nmax + 5];
bool *sel[nmax + 5];

vector<int> c;

int get_poz(int val)
{
    int st = 0;
    int dr = c.size() - 1;
    int poz = 0;
    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(c[mij] <= val)
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    return poz;
}

void Dijkstra(int x, int y)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=c.size()+3;j++)
        {
            d[i][j] = oo;
            sel[i][j] = false;
        }
    }
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> h;
    d[x][y] = 0;
    h.push({0,{x, y}});
    while(!h.empty())
    {
        while(!h.empty() && sel[h.top().second.first][h.top().second.second])
        {
            h.pop();
        }
        if(h.empty())
        {
            break;
        }
        x = h.top().second.first;
        y = h.top().second.second;
        h.pop();
        sel[x][y] = true;

        /// sus
        if(x != 1)
        {
            if(c[y] <= l[x - 1])
            {
                if(1 + d[x][y] < d[x - 1][y])
                {
                    d[x - 1][y] = 1 + d[x][y];
                    h.push({d[x - 1][y], {x - 1, y}});
                }
            }
            else
            {
                int yy = get_poz(l[x - 1]);
                if(d[x][y] + 1 < d[x - 1][yy])
                {
                    d[x - 1][yy] = 1 + d[x][y];
                    h.push({d[x - 1][yy], {x - 1, yy}});
                }
            }
        }

        /// jos
        if(x != n)
        {
            if(c[y] <= l[x + 1])
            {
                if(1 + d[x][y] < d[x + 1][y])
                {
                    d[x + 1][y] = 1 + d[x][y];
                    h.push({d[x + 1][y], {x + 1, y}});
                }
            }
            else
            {
                int yy = get_poz(l[x + 1]);
                if(d[x][y] + 1 < d[x + 1][yy])
                {
                    d[x + 1][yy] = 1 + d[x][y];
                    h.push({d[x + 1][yy], {x + 1, yy}});
                }
            }
        }

        /// stanga
        if(y == 0)
        {
            if(x != 1)
            {
                int yy = get_poz(l[x - 1]);
                if(d[x][y] + 1 < d[x - 1][yy])
                {
                    d[x - 1][yy] = 1 + d[x][y];
                    h.push({d[x - 1][yy], {x - 1, yy}});
                }
            }
        }
        else
        {
            if(d[x][y] + c[y] - c[y - 1] < d[x][y - 1])
            {
                d[x][y - 1] = d[x][y] + c[y] - c[y - 1];
                h.push({d[x][y - 1], {x, y - 1}});
            }
        }

        /// dreapta
        if(c[y] == l[x])
        {
            if(x != n)
            {
                if(d[x][y] + 1 < d[x + 1][0])
                {
                    d[x + 1][0] = 1 + d[x][y];
                    h.push({d[x + 1][0], {x + 1, 0}});
                }
            }
        }
        else
        {
            if(d[x][y] + c[y + 1] - c[y] < d[x][y + 1])
            {
                d[x][y + 1] = d[x][y] + c[y + 1] - c[y];
                h.push({d[x][y + 1], {x, y + 1}});
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n;
    cin>>sl>>sc;
    cin>>el>>ec;
    --sc;
    --ec;
    c.push_back(0);
    c.push_back(sc);
    c.push_back(ec);
    for(int i=1; i<=n; i++)
    {
        cin>>l[i];
        c.push_back(l[i]);
    }

    sort(c.begin(),c.end());
    vector<int> aux = c;
    c.clear();
    for(auto it : aux)
    {
        if(c.empty() || (it != c.back()))
        {
            c.push_back(it);
        }
    }
    for(int i=1;i<=n;i++)
    {
        d[i] = new int[(int)c.size() + 5];
        sel[i] = new bool[(int)c.size() + 5];
    }
    sc = get_poz(sc);
    ec = get_poz(ec);
    Dijkstra(sl, sc);
    cout<<d[el][ec]<<'\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void Dijkstra(long long int, long long int)':
Main.cpp:44:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int j=0;j<=c.size()+3;j++)
      |                     ~^~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 26 / 26
• Subtask 4: 11 / 11
• Subtask 5: 0 / 44