Submission #779499

#	Time	Username	Problem	Language	Result	Execution time	Memory
779499		Tenis0206	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	784 ms	50648 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int oo = INT_MAX;
const int nmax = 3e4;
const int bsize = 173;

int n,m;
int b[nmax + 5], p[nmax + 5];

int r[nmax + 5][bsize + 5];

int d[nmax + 5], d_l[nmax + 5][bsize + 5];
bool sel[nmax + 5], sel_l[nmax + 5][bsize + 5];

vector<int> l[nmax + 5];

typedef pair<int,pair<int,int>> pi;

priority_queue <pi,vector<pi>,greater<pi>> h;

void switch_doge(int t, int poz)
{
    sel[poz] = true;
    d[poz] = t;
    for(auto ln : l[poz])
    {
        if(ln < bsize)
        {
            if(poz - ln >= 0 && t + 1 < d_l[poz - ln][ln])
            {
                d_l[poz - ln][ln] = t + 1;
                h.push({t + 1, {poz - ln, ln}});
            }
            if(poz + ln < n && t + 1 < d_l[poz + ln][ln])
            {
                d_l[poz + ln][ln] = t + 1;
                h.push({t + 1, {poz + ln, ln}});
            }
        }
        else
        {
            for(int i=poz;i>=0;i-=ln)
            {
                int t_aux = t + (poz - i) / ln;
                if(t_aux < d[i])
                {
                    d[i] = t_aux;
                    h.push({t_aux,{i,ln}});
                }
            }
            for(int i=poz+ln;i<n;i+=ln)
            {
                int t_aux = t + (i - poz) / ln;
                if(t_aux < d[i])
                {
                    d[i] = t_aux;
                    h.push({t_aux,{i,ln}});
                }
            }
        }
    }
}

int 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>>m;
    for(int i=0; i<n; i++)
    {
        d[i] = oo;
        for(int ln=1; ln<bsize; ln++)
        {
            r[i][ln] = oo;
            d_l[i][ln] = oo;
        }
    }
    for(int i=0; i<m; i++)
    {
        cin>>b[i]>>p[i];
        l[b[i]].push_back(p[i]);
    }
    h.push({0,{b[0],p[0]}});
    if(b[0] < bsize)
    {
        d_l[b[0]][p[0]] = 0;
    }
    while(!h.empty())
    {
        while(!h.empty())
        {
            int poz = h.top().second.first;
            int ln = h.top().second.second;
            if(ln < bsize)
            {
                if(sel_l[poz][ln])
                {
                    h.pop();
                    continue;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if(sel[poz])
                {
                    h.pop();
                    continue;
                }
                else
                {
                    break;
                }
            }
        }
        if(h.empty())
        {
            break;
        }
        int t = h.top().first;
        int poz = h.top().second.first;
        int ln = h.top().second.second;
        h.pop();
        if(!sel[poz])
        {
            switch_doge(t,poz);
        }
        if(ln < bsize)
        {
            sel_l[poz][ln] = true;
            if(poz - ln >= 0 && t + 1 < d_l[poz - ln][ln])
            {
                d_l[poz - ln][ln] = 1 + t;
                h.push({1 + t, {poz - ln, ln}});
            }
            if(poz + ln < n && t + 1 < d_l[poz + ln][ln])
            {
                d_l[poz + ln][ln] = 1 + t;
                h.push({1 + t, {poz + ln, ln}});
            }
        }
    }
    int rez = d[b[1]];
    if(rez==oo)
    {
        cout<<-1<<'\n';
        return 0;
    }
    cout<<rez<<'\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43