Submission #874345

# Submission time Handle Problem Language Result Execution time Memory
874345 2023-11-16T17:20:52 Z andrei_boaca Sky Walking (IOI19_walk) C++17
0 / 100
1517 ms 196824 KB
#include "walk.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("fast-math")
#define int long long
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll INF=1e18;
map<pii,int> f;
int cnt;
vector<pii> muchii[3000005];
vector<pii> nodes;
vector<int> whovert[100005],whooriz[100005];
int arb[4*100005],toprop[4*100005];
int n,m;
struct skywalk
{
    ll l,r,h,ind;
} v[100005];
vector<signed> X,H,L,R,Y;
bool Hdesc(int a,int b)
{
    return H[a]>H[b];
}
bool Hcresc(skywalk a, skywalk b)
{
    return a.h<b.h;
}
void addnode(int i,int j)
{
    if(f.count({X[i],Y[j]})!=0)
        return;
    //cout<<X[i]<<' '<<Y[j]<<'\n';
    cnt++;
    f[{X[i],Y[j]}]=cnt;
    nodes.push_back({i,j});
    whovert[i].push_back(Y[j]);
    whooriz[j].push_back(X[i]);
}
bool cresc(pii a,pii b)
{
    return Y[a.second]<Y[b.second];
}
bool use[3000005];
ll dist[3000005];
ll bfs(ll s,ll g)
{
    priority_queue<pll,vector<pll>,greater<pll>> coada;
    for(int i=1;i<=cnt;i++)
    {
        dist[i]=INF;
        if(nodes[i].first==s)
        {
            dist[i]=Y[nodes[i].second];
            coada.push({dist[i],i});
        }
    }
    ll ans=INF;
    while(!coada.empty())
    {
        int nod=coada.top().second;
        coada.pop();
        if(nodes[nod].first==g)
            ans=min(ans,dist[nod]+Y[nodes[nod].second]);
        if(use[nod])
            continue;
        use[nod]=1;
        for(auto i:muchii[nod])
            if(dist[i.first]>dist[nod]+i.second)
            {
                dist[i.first]=dist[nod]+i.second;
                coada.push({dist[i.first],i.first});
            }
    }
    if(ans==INF)
        return -1;
    return ans;
}
void prop(int nod)
{
    int val=toprop[nod];
    arb[nod*2]=val;
    arb[nod*2+1]=val;
    toprop[nod*2]=val;
    toprop[nod*2+1]=val;
}
void build(int nod,int st,int dr)
{
    arb[nod]=-1;
    toprop[nod]=-1;
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void update(int nod,int st,int dr,int a,int b,int val)
{
    if(toprop[nod]!=-1&&st!=dr)
        prop(nod);
    toprop[nod]=-1;
    if(st>=a&&dr<=b)
    {
        arb[nod]=val;
        toprop[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(nod*2,st,mij,a,b,val);
    if(b>mij)
        update(nod*2+1,mij+1,dr,a,b,val);
}
int query(int nod,int st,int dr,int poz)
{
    if(toprop[nod]!=-1&&st!=dr)
        prop(nod);
    toprop[nod]=-1;
    if(st==dr)
        return arb[nod];
    int mij=(st+dr)/2;
    if(poz<=mij)
        return query(nod*2,st,mij,poz);
    else
        return query(nod*2+1,mij+1,dr,poz);
}
long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g)
{
    X=x;
    H=h;
    L=l;
    R=r;
    Y=y;
    n=x.size();
    m=l.size();
    nodes.push_back({0,0});
    for(int i=0;i<m;i++)
        v[i]={l[i],r[i],y[i],i};
    vector<int> ups;
    for(int i=0;i<n;i++)
        ups.push_back(i);
    sort(ups.begin(),ups.end(),Hdesc);
    sort(v,v+m,Hcresc);
    set<int> setik;
    for(int i=0;i<n;i++)
        setik.insert(i);
    for(int i=0;i<m;i++)
    {
        while(!ups.empty()&&H[ups.back()]<v[i].h)
        {
            setik.erase(ups.back());
            ups.pop_back();
        }
        addnode(v[i].l,v[i].ind);
        addnode(v[i].r,v[i].ind);
        if(setik.find(s)!=setik.end())
        {
            if(s>=v[i].l&&s<=v[i].r)
                addnode(s,v[i].ind);
        }
        else
        {
            auto it=setik.lower_bound(s);
            if(it!=setik.end())
            {
                if((*it)>=v[i].l&&(*it)<=v[i].r)
                    addnode((*it),v[i].ind);
            }
            if(it!=setik.begin())
            {
                it=prev(it);
                if((*it)>=v[i].l&&(*it)<=v[i].r)
                    addnode((*it),v[i].ind);
            }
        }
        if(setik.find(g)!=setik.end())
        {
            if(g>=v[i].l&&g<=v[i].r)
                addnode(g,v[i].ind);
        }
        else
        {
            auto it=setik.lower_bound(g);
            if(it!=setik.end())
            {
                if((*it)>=v[i].l&&(*it)<=v[i].r)
                    addnode((*it),v[i].ind);
            }
            if(it!=setik.begin())
            {
                it=prev(it);
                if((*it)>=v[i].l&&(*it)<=v[i].r)
                    addnode((*it),v[i].ind);
            }
        }
    }
    vector<pii> ord=nodes;
    sort(ord.begin(),ord.end(),cresc);
    build(1,0,n-1);
    int poz=0;
    for(auto i:ord)
    {
        while(poz<m&&v[poz].h<Y[i.second])
        {
            update(1,0,n-1,v[poz].l,v[poz].r,v[poz].ind);
            poz++;
        }
        int val=query(1,0,n-1,i.first);
        if(val!=-1)
        {
            if(Y[val]<=H[i.first])
                addnode(i.first,val);
        }
    }

    reverse(ord.begin(),ord.end());
    reverse(v,v+m);
    build(1,0,n-1);
    poz=0;
    for(auto i:ord)
    {
        while(poz<m&&v[poz].h>Y[i.second])
        {
            update(1,0,n-1,v[poz].l,v[poz].r,v[poz].ind);
            poz++;
        }
        int val=query(1,0,n-1,i.first);
        if(val!=-1)
        {
            if(Y[val]<=H[i.first])
                addnode(i.first,val);
        }
    }

    for(int i=0;i<n;i++)
    {
        sort(whovert[i].begin(),whovert[i].end());
        for(int j=1;j<whovert[i].size();j++)
        {
            int ya=whovert[i][j-1];
            int yb=whovert[i][j];
            int a=f[{X[i],ya}];
            int b=f[{X[i],yb}];
            muchii[a].push_back({b,yb-ya});
            muchii[b].push_back({a,yb-ya});
        }
    }

    for(int i=0;i<m;i++)
    {
        sort(whooriz[i].begin(),whooriz[i].end());
        for(int j=1;j<whooriz[i].size();j++)
        {
            int xa=whooriz[i][j-1];
            int xb=whooriz[i][j];
            int a=f[{xa,Y[i]}];
            int b=f[{xb,Y[i]}];
            muchii[a].push_back({b,xb-xa});
            muchii[b].push_back({a,xb-xa});
        }
    }

    return bfs(s,g);
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:242:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |         for(int j=1;j<whovert[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~
walk.cpp:256:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  256 |         for(int j=1;j<whooriz[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 22 ms 82280 KB Output is correct
2 Correct 17 ms 82392 KB Output is correct
3 Incorrect 18 ms 82520 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 18 ms 82476 KB Output is correct
2 Correct 17 ms 82524 KB Output is correct
3 Correct 1290 ms 181632 KB Output is correct
4 Correct 1399 ms 186908 KB Output is correct
5 Correct 859 ms 165556 KB Output is correct
6 Correct 805 ms 158304 KB Output is correct
7 Correct 872 ms 165860 KB Output is correct
8 Correct 1480 ms 190440 KB Output is correct
9 Correct 1224 ms 179800 KB Output is correct
10 Correct 1514 ms 190876 KB Output is correct
11 Correct 1043 ms 162248 KB Output is correct
12 Correct 648 ms 134104 KB Output is correct
13 Correct 1517 ms 196824 KB Output is correct
14 Correct 489 ms 131564 KB Output is correct
15 Incorrect 494 ms 133724 KB Output isn't correct
16 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 101320 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 101320 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 22 ms 82280 KB Output is correct
2 Correct 17 ms 82392 KB Output is correct
3 Incorrect 18 ms 82520 KB Output isn't correct
4 Halted 0 ms 0 KB -