oj.uz

Submission #1026837

# Submission time Handle Problem Language Result Execution time Memory
1026837 2024-07-18T12:15:30 Z hotboy2703 Sky Walking (IOI19_walk) C++17
33 / 100
 642 ms 149396 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
struct walk{
    ll l,r,y;
};
vector <walk> all;
const ll MAXN = 1e5 + 100;
const ll INF = 1e18;
vector <pll> g[MAXN*20];
ll dist[MAXN*20];
ll dijkstra(ll s,ll t){
    memset(dist,0x3f,sizeof dist);
    dist[s] = 0;
    priority_queue <pll,vector <pll> ,greater <> > q;
    q.push(MP(dist[s],s));
    while (!q.empty()){
        auto u = q.top().se;
        ll val = q.top().fi;
        q.pop();
        if (dist[u] != val)continue;
        for (auto tmp:g[u]){
            ll v = tmp.fi,w = tmp.se;
            if (dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                q.push(MP(dist[v],v));
            }
        }
    }
    if (dist[t] >=INF)dist[t] = -1;
    return dist[t];
}
ll SUSSYBAKA;
struct point{
    ll x,y,id;
    point(ll x1=-1,ll y1=-1):x(x1),y(y1),id(x1==-1?-1:SUSSYBAKA++){
    }
    bool operator < (const point &p)const {
        return MP(x,y)<MP(p.x,p.y);
    }
    bool operator == (const point &p)const {
        return MP(x,y)==MP(p.x,p.y);
    }
};
vector <point> vertices;
long long min_distance(std::vector<int> X, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int S, int G){
    ll m = sz(l);
    ll n = sz(X);
    for (ll i = 0;i < m;i ++){
        all.push_back({l[i],r[i],y[i]});
    }
    sort(all.begin(),all.end(),[](walk a1,walk a2){return a1.y<a2.y;});
    vector <ll> order;
    order.resize(n);
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](ll x,ll y){return h[x] > h[y];});
    vertices.emplace_back(X[S],0);
    vertices.emplace_back(X[G],0);
    for (auto x:all){
        vertices.emplace_back(X[x.l],x.y);
        vertices.emplace_back(X[x.r],x.y);
    }
    auto add_vertex = [&](bool inv){
        vector <ll> bd;
        for (ll i = inv?n-1:0;inv?i>=0:i<n;inv?i--:i++){
//            cout<<i<<endl;
            if (sz(bd) && h[bd.back()] < h[i])bd.pop_back();
            bd.push_back(i);
            if (i==S||i==G){
                ll ptr = sz(bd)-1;
                for (auto x:all){
                    while (ptr>=0&&h[bd[ptr]] < x.y)ptr--;
                    if (ptr != -1 && x.l <= bd[ptr] && bd[ptr] <= x.r){
                        vertices.emplace_back(X[bd[ptr]],x.y);
                    }
                }
            }
        }
    };
    add_vertex(0);
    add_vertex(1);
//    return -1;
    vector <pair <pll,bool> > event;
    for (auto x:all){
        event.emplace_back(MP(X[x.l],x.y),1);
        event.emplace_back(MP(X[x.r]+1,x.y),0);
    }
    sort(event.begin(),event.end());
    sort(vertices.begin(),vertices.end());
    vertices.resize(unique(vertices.begin(),vertices.end())-vertices.begin());

    {
        ll ptr = 0;
        multiset <ll> ms;
        vector <pll> Tm;
        for (auto x:vertices){
            while (ptr<sz(event) && event[ptr].fi.fi <= x.x){
                if (event[ptr].se)ms.insert(event[ptr].fi.se);
                else ms.erase(ms.find((event[ptr].fi.se)));
                ptr++;
            }
            auto tmp = ms.upper_bound(x.y);
            if (tmp != ms.end())Tm.emplace_back(x.x,*(tmp));
            tmp = ms.lower_bound(x.y);
            if (tmp != ms.begin())Tm.emplace_back(x.x,*prev(tmp));
        }
        for (auto x:Tm)vertices.emplace_back(x.fi,x.se);
    }
    sort(vertices.begin(),vertices.end());
    vertices.resize(unique(vertices.begin(),vertices.end())-vertices.begin());
    auto add_edge = [&](point a1,point a2){
        ll w = abs(a1.x-a2.x) + abs(a1.y-a2.y);
        g[a1.id].push_back(MP(a2.id,w));
        g[a2.id].push_back(MP(a1.id,w));
    };

    for (ll j = 0;j + 1 < sz(vertices);j ++){
        if (vertices[j].x == vertices[j+1].x)add_edge(vertices[j],vertices[j+1]);
    }
    auto cmp_y = [](point a1,point a2){return MP(a1.y,a1.x) < MP(a2.y,a2.x);};
    sort(vertices.begin(),vertices.end(),cmp_y);
    auto fi = [&](pll x){
        return lower_bound(vertices.begin(),vertices.end(),x,
                           [](point a1,pll val){return MP(a1.y,a1.x) < MP(val.se,val.fi);})-vertices.begin();
    };
    vector <ll> cnt(sz(vertices));
    for (auto x:all){
        cnt[fi(MP(X[x.l],x.y))] ++;
        cnt[fi(MP(X[x.r],x.y))] --;
    }
    for (ll i = 0;i < sz(vertices);i ++){
        if (i)cnt[i]+=cnt[i-1];
        if (cnt[i]){
            add_edge(vertices[i],vertices[i+1]);
        }
    }
    for (ll i = 0;i < sz(vertices);i ++){
        if (MP(vertices[i].x,vertices[i].y) == MP(ll(X[S]),0LL))S = vertices[i].id;
        if (MP(vertices[i].x,vertices[i].y) == MP(ll(X[G]),0LL))G = vertices[i].id;

    }
    return dijkstra(S,G);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 63064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 63068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 76272 KB Output is correct
2 Correct 492 ms 138984 KB Output is correct
3 Correct 498 ms 140560 KB Output is correct
4 Correct 607 ms 146284 KB Output is correct
5 Correct 641 ms 148492 KB Output is correct
6 Correct 581 ms 142292 KB Output is correct
7 Correct 288 ms 107320 KB Output is correct
8 Correct 227 ms 97592 KB Output is correct
9 Correct 558 ms 136988 KB Output is correct
10 Correct 248 ms 114216 KB Output is correct
11 Correct 19 ms 64324 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 76272 KB Output is correct
2 Correct 492 ms 138984 KB Output is correct
3 Correct 498 ms 140560 KB Output is correct
4 Correct 607 ms 146284 KB Output is correct
5 Correct 641 ms 148492 KB Output is correct
6 Correct 581 ms 142292 KB Output is correct
7 Correct 288 ms 107320 KB Output is correct
8 Correct 227 ms 97592 KB Output is correct
9 Correct 558 ms 136988 KB Output is correct
10 Correct 248 ms 114216 KB Output is correct
11 Correct 19 ms 64324 KB Output is correct
12 Correct 519 ms 141596 KB Output is correct
13 Correct 445 ms 144288 KB Output is correct
14 Correct 637 ms 149396 KB Output is correct
15 Correct 444 ms 126404 KB Output is correct
16 Correct 462 ms 133972 KB Output is correct
17 Correct 529 ms 146252 KB Output is correct
18 Correct 451 ms 126124 KB Output is correct
19 Correct 466 ms 135872 KB Output is correct
20 Correct 282 ms 104712 KB Output is correct
21 Correct 35 ms 66200 KB Output is correct
22 Correct 472 ms 128892 KB Output is correct
23 Correct 424 ms 127232 KB Output is correct
24 Correct 328 ms 115828 KB Output is correct
25 Correct 392 ms 121976 KB Output is correct
26 Correct 289 ms 114580 KB Output is correct
27 Correct 642 ms 147432 KB Output is correct
28 Correct 454 ms 144272 KB Output is correct
29 Correct 611 ms 144608 KB Output is correct
30 Correct 279 ms 106644 KB Output is correct
31 Correct 550 ms 138408 KB Output is correct
32 Correct 231 ms 107776 KB Output is correct
33 Correct 244 ms 113108 KB Output is correct
34 Correct 261 ms 116828 KB Output is correct
35 Correct 311 ms 116848 KB Output is correct
36 Correct 243 ms 108232 KB Output is correct
37 Correct 216 ms 102996 KB Output is correct
38 Correct 252 ms 114324 KB Output is correct
39 Correct 297 ms 118768 KB Output is correct
40 Correct 260 ms 111156 KB Output is correct
41 Correct 231 ms 104580 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 63064 KB Output isn't correct
2 Halted 0 ms 0 KB -