Submission #779476

#	Time	Username	Problem	Language	Result	Execution time	Memory
779476		Tenis0206	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	22 / 100	6 ms	5844 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];

set<pair<int,int>> s[nmax + 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
        {
            if(poz - ln >= 0)
            {
                auto it = s[poz - ln].lower_bound({ln,0});
                if(t + 1 < it -> second)
                {
                    s[poz - ln].erase(it);
                    s[poz - ln].insert({ln, t + 1});
                    h.push({t + 1, {poz - ln, ln}});
                }
            }
            if(poz + ln < n)
            {
                auto it = s[poz + ln].lower_bound({ln,0});
                if(t + 1 < it -> second)
                {
                    s[poz + ln].erase(it);
                    s[poz + ln].insert({ln, t + 1});
                    h.push({t + 1, {poz + ln, 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];
        if(p[i] >= bsize)
        {
            for(int j=b[i]; j>=0; j-=p[i])
            {
                s[j].insert({p[i],oo});
            }
            for(int j=b[i]+p[i]; j<n; j+=p[i])
            {
                s[j].insert({p[i],oo});
            }
        }
        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;
    }
    else
    {
        auto it = s[b[0]].lower_bound({p[0],0});
        s[b[0]].erase(it);
        s[b[0]].insert({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
            {
                auto it = s[poz].lower_bound({ln,0});
                if(it==s[poz].end())
                {
                    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}});
            }
        }
        else
        {
            auto er = s[poz].lower_bound({ln,0});
            s[poz].erase(er);
            if(poz - ln >= 0)
            {
                auto it = s[poz - ln].lower_bound({ln,0});
                if(t + 1 < it -> second)
                {
                    s[poz - ln].erase(it);
                    s[poz - ln].insert({ln, 1 + t});
                    h.push({1 + t, {poz - ln, ln}});
                }
            }
            if(poz + ln < n)
            {
                auto it = s[poz + ln].lower_bound({ln,0});
                if(t + 1 < it -> second)
                {
                    s[poz + ln].erase(it);
                    s[poz + ln].insert({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: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43