oj.uz

답안 #779476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779476 2023-07-11T13:10:44 Z Tenis0206 Jakarta Skyscrapers (APIO15_skyscraper) C++11
22 / 100
 6 ms 5844 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 2 ms 2388 KB Output is correct
3 Correct 2 ms 2388 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 2 ms 2388 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 2 ms 2388 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2436 KB Output is correct
2 Correct 2 ms 2388 KB Output is correct
3 Correct 1 ms 2388 KB Output is correct
4 Correct 2 ms 2440 KB Output is correct
5 Correct 2 ms 2388 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 2 ms 2388 KB Output is correct
8 Correct 2 ms 2440 KB Output is correct
9 Correct 2 ms 2572 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2572 KB Output is correct
14 Correct 3 ms 2700 KB Output is correct
15 Correct 2 ms 2700 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 2 ms 2444 KB Output is correct
3 Correct 2 ms 2388 KB Output is correct
4 Correct 1 ms 2388 KB Output is correct
5 Correct 1 ms 2388 KB Output is correct
6 Correct 2 ms 2436 KB Output is correct
7 Correct 2 ms 2436 KB Output is correct
8 Correct 2 ms 2516 KB Output is correct
9 Correct 1 ms 2516 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2700 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct
16 Correct 2 ms 2700 KB Output is correct
17 Correct 4 ms 3796 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5332 KB Output is correct
20 Correct 4 ms 5716 KB Output is correct
21 Correct 3 ms 3028 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 5140 KB Output is correct
24 Correct 6 ms 5784 KB Output is correct
25 Correct 4 ms 5844 KB Output is correct
26 Correct 3 ms 5588 KB Output is correct
27 Correct 3 ms 5716 KB Output is correct
28 Incorrect 3 ms 5588 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2440 KB Output is correct
2 Correct 1 ms 2436 KB Output is correct
3 Correct 1 ms 2440 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 2 ms 2388 KB Output is correct
6 Correct 1 ms 2388 KB Output is correct
7 Correct 2 ms 2388 KB Output is correct
8 Correct 1 ms 2516 KB Output is correct
9 Correct 2 ms 2568 KB Output is correct
10 Correct 2 ms 2568 KB Output is correct
11 Correct 2 ms 2724 KB Output is correct
12 Correct 2 ms 2576 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct
16 Correct 2 ms 2704 KB Output is correct
17 Correct 5 ms 3808 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5332 KB Output is correct
20 Correct 3 ms 5656 KB Output is correct
21 Correct 2 ms 3028 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 4 ms 5076 KB Output is correct
24 Correct 5 ms 5776 KB Output is correct
25 Correct 5 ms 5844 KB Output is correct
26 Correct 3 ms 5588 KB Output is correct
27 Correct 3 ms 5716 KB Output is correct
28 Incorrect 3 ms 5460 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 2 ms 2388 KB Output is correct
3 Correct 1 ms 2448 KB Output is correct
4 Correct 2 ms 2436 KB Output is correct
5 Correct 1 ms 2432 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 2 ms 2440 KB Output is correct
8 Correct 1 ms 2516 KB Output is correct
9 Correct 1 ms 2516 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2704 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2696 KB Output is correct
17 Correct 6 ms 3860 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 5 ms 5260 KB Output is correct
20 Correct 4 ms 5652 KB Output is correct
21 Correct 2 ms 3028 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct
23 Correct 4 ms 5076 KB Output is correct
24 Correct 6 ms 5716 KB Output is correct
25 Correct 4 ms 5844 KB Output is correct
26 Correct 3 ms 5588 KB Output is correct
27 Correct 3 ms 5648 KB Output is correct
28 Incorrect 3 ms 5460 KB Output isn't correct
29 Halted 0 ms 0 KB -