oj.uz

Submission #1026820

# Submission time Handle Problem Language Result Execution time Memory
1026820 2024-07-18T12:05:39 Z hotboy2703 Sky Walking (IOI19_walk) C++14
15 / 100
 650 ms 148412 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];});
//    cout<<"OK"<<endl;
    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 (x.l <= ptr && ptr <= x.r){
                        vertices.emplace_back(X[bd[ptr]],all[i].y);
                    }
                }
            }
        }
    };
    add_vertex(0);
    add_vertex(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());

//    return -1;
    {
        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]){
//            assert(i != sz(vertices)-1);
            add_edge(vertices[i],vertices[i+1]);
        }
    }
//    for (auto x:vertices)cout<<"SUS "<<x.x<<' '<<x.y<<' '<<x.id<<endl;
    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 10 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 10 ms 62944 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 74 ms 76704 KB Output is correct
2 Correct 466 ms 139428 KB Output is correct
3 Correct 511 ms 140820 KB Output is correct
4 Correct 582 ms 145516 KB Output is correct
5 Correct 629 ms 148144 KB Output is correct
6 Correct 561 ms 141408 KB Output is correct
7 Correct 256 ms 106672 KB Output is correct
8 Correct 228 ms 98572 KB Output is correct
9 Correct 538 ms 137408 KB Output is correct
10 Correct 230 ms 112404 KB Output is correct
11 Correct 21 ms 64324 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 76704 KB Output is correct
2 Correct 466 ms 139428 KB Output is correct
3 Correct 511 ms 140820 KB Output is correct
4 Correct 582 ms 145516 KB Output is correct
5 Correct 629 ms 148144 KB Output is correct
6 Correct 561 ms 141408 KB Output is correct
7 Correct 256 ms 106672 KB Output is correct
8 Correct 228 ms 98572 KB Output is correct
9 Correct 538 ms 137408 KB Output is correct
10 Correct 230 ms 112404 KB Output is correct
11 Correct 21 ms 64324 KB Output is correct
12 Correct 496 ms 142096 KB Output is correct
13 Correct 424 ms 144164 KB Output is correct
14 Correct 650 ms 148412 KB Output is correct
15 Correct 422 ms 128392 KB Output is correct
16 Correct 446 ms 134568 KB Output is correct
17 Correct 517 ms 147248 KB Output is correct
18 Correct 461 ms 126512 KB Output is correct
19 Correct 438 ms 135884 KB Output is correct
20 Correct 274 ms 104840 KB Output is correct
21 Runtime error 63 ms 104192 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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