oj.uz

Submission #874351

# Submission time Handle Problem Language Result Execution time Memory
874351 2023-11-16T17:32:13 Z andrei_boaca Sky Walking (IOI19_walk) C++17
100 / 100
 3125 ms 257576 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")
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<int> 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)
{
    //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<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int 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:239:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |         for(int j=1;j<whovert[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~
walk.cpp:253:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |         for(int j=1;j<whooriz[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 81372 KB Output is correct
2 Correct 17 ms 81244 KB Output is correct
3 Correct 18 ms 81444 KB Output is correct
4 Correct 17 ms 81240 KB Output is correct
5 Correct 19 ms 81500 KB Output is correct
6 Correct 18 ms 81500 KB Output is correct
7 Correct 19 ms 81500 KB Output is correct
8 Correct 18 ms 81500 KB Output is correct
9 Correct 17 ms 81240 KB Output is correct
10 Correct 18 ms 81500 KB Output is correct
11 Correct 18 ms 81240 KB Output is correct
12 Correct 18 ms 81460 KB Output is correct
13 Correct 18 ms 81244 KB Output is correct
14 Correct 18 ms 81428 KB Output is correct
15 Correct 18 ms 81496 KB Output is correct
16 Correct 18 ms 81240 KB Output is correct
17 Correct 18 ms 81496 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 81244 KB Output is correct
2 Correct 18 ms 81244 KB Output is correct
3 Correct 1314 ms 165736 KB Output is correct
4 Correct 1392 ms 163432 KB Output is correct
5 Correct 813 ms 146092 KB Output is correct
6 Correct 859 ms 147316 KB Output is correct
7 Correct 847 ms 145992 KB Output is correct
8 Correct 1380 ms 170764 KB Output is correct
9 Correct 1226 ms 159736 KB Output is correct
10 Correct 1446 ms 170148 KB Output is correct
11 Correct 1050 ms 155596 KB Output is correct
12 Correct 779 ms 137152 KB Output is correct
13 Correct 1545 ms 168768 KB Output is correct
14 Correct 762 ms 165648 KB Output is correct
15 Correct 761 ms 162096 KB Output is correct
16 Correct 671 ms 145016 KB Output is correct
17 Correct 737 ms 140588 KB Output is correct
18 Correct 1020 ms 229744 KB Output is correct
19 Correct 39 ms 86988 KB Output is correct
20 Correct 276 ms 123324 KB Output is correct
21 Correct 733 ms 145240 KB Output is correct
22 Correct 669 ms 138176 KB Output is correct
23 Correct 730 ms 163412 KB Output is correct
24 Correct 669 ms 141300 KB Output is correct
25 Correct 728 ms 142168 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 109936 KB Output is correct
2 Correct 1594 ms 181832 KB Output is correct
3 Correct 1774 ms 186156 KB Output is correct
4 Correct 2069 ms 196648 KB Output is correct
5 Correct 2005 ms 198788 KB Output is correct
6 Correct 1972 ms 198508 KB Output is correct
7 Correct 804 ms 146620 KB Output is correct
8 Correct 733 ms 143608 KB Output is correct
9 Correct 1876 ms 198744 KB Output is correct
10 Correct 811 ms 171716 KB Output is correct
11 Correct 38 ms 85708 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 109936 KB Output is correct
2 Correct 1594 ms 181832 KB Output is correct
3 Correct 1774 ms 186156 KB Output is correct
4 Correct 2069 ms 196648 KB Output is correct
5 Correct 2005 ms 198788 KB Output is correct
6 Correct 1972 ms 198508 KB Output is correct
7 Correct 804 ms 146620 KB Output is correct
8 Correct 733 ms 143608 KB Output is correct
9 Correct 1876 ms 198744 KB Output is correct
10 Correct 811 ms 171716 KB Output is correct
11 Correct 38 ms 85708 KB Output is correct
12 Correct 1761 ms 183824 KB Output is correct
13 Correct 1934 ms 189256 KB Output is correct
14 Correct 2145 ms 193688 KB Output is correct
15 Correct 1256 ms 171176 KB Output is correct
16 Correct 1524 ms 178692 KB Output is correct
17 Correct 1630 ms 191132 KB Output is correct
18 Correct 1332 ms 171220 KB Output is correct
19 Correct 1462 ms 177724 KB Output is correct
20 Correct 866 ms 141504 KB Output is correct
21 Correct 89 ms 91080 KB Output is correct
22 Correct 1164 ms 166412 KB Output is correct
23 Correct 1068 ms 163616 KB Output is correct
24 Correct 757 ms 146940 KB Output is correct
25 Correct 999 ms 158064 KB Output is correct
26 Correct 581 ms 135160 KB Output is correct
27 Correct 2142 ms 194516 KB Output is correct
28 Correct 1762 ms 188340 KB Output is correct
29 Correct 2027 ms 192148 KB Output is correct
30 Correct 789 ms 141972 KB Output is correct
31 Correct 1894 ms 192956 KB Output is correct
32 Correct 708 ms 158832 KB Output is correct
33 Correct 697 ms 150216 KB Output is correct
34 Correct 780 ms 165052 KB Output is correct
35 Correct 903 ms 153904 KB Output is correct
36 Correct 799 ms 148060 KB Output is correct
37 Correct 744 ms 145400 KB Output is correct
38 Correct 672 ms 138148 KB Output is correct
39 Correct 706 ms 162832 KB Output is correct
40 Correct 689 ms 141240 KB Output is correct
41 Correct 733 ms 142380 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 81372 KB Output is correct
2 Correct 17 ms 81244 KB Output is correct
3 Correct 18 ms 81444 KB Output is correct
4 Correct 17 ms 81240 KB Output is correct
5 Correct 19 ms 81500 KB Output is correct
6 Correct 18 ms 81500 KB Output is correct
7 Correct 19 ms 81500 KB Output is correct
8 Correct 18 ms 81500 KB Output is correct
9 Correct 17 ms 81240 KB Output is correct
10 Correct 18 ms 81500 KB Output is correct
11 Correct 18 ms 81240 KB Output is correct
12 Correct 18 ms 81460 KB Output is correct
13 Correct 18 ms 81244 KB Output is correct
14 Correct 18 ms 81428 KB Output is correct
15 Correct 18 ms 81496 KB Output is correct
16 Correct 18 ms 81240 KB Output is correct
17 Correct 18 ms 81496 KB Output is correct
18 Correct 18 ms 81244 KB Output is correct
19 Correct 18 ms 81244 KB Output is correct
20 Correct 1314 ms 165736 KB Output is correct
21 Correct 1392 ms 163432 KB Output is correct
22 Correct 813 ms 146092 KB Output is correct
23 Correct 859 ms 147316 KB Output is correct
24 Correct 847 ms 145992 KB Output is correct
25 Correct 1380 ms 170764 KB Output is correct
26 Correct 1226 ms 159736 KB Output is correct
27 Correct 1446 ms 170148 KB Output is correct
28 Correct 1050 ms 155596 KB Output is correct
29 Correct 779 ms 137152 KB Output is correct
30 Correct 1545 ms 168768 KB Output is correct
31 Correct 762 ms 165648 KB Output is correct
32 Correct 761 ms 162096 KB Output is correct
33 Correct 671 ms 145016 KB Output is correct
34 Correct 737 ms 140588 KB Output is correct
35 Correct 1020 ms 229744 KB Output is correct
36 Correct 39 ms 86988 KB Output is correct
37 Correct 276 ms 123324 KB Output is correct
38 Correct 733 ms 145240 KB Output is correct
39 Correct 669 ms 138176 KB Output is correct
40 Correct 730 ms 163412 KB Output is correct
41 Correct 669 ms 141300 KB Output is correct
42 Correct 728 ms 142168 KB Output is correct
43 Correct 248 ms 109936 KB Output is correct
44 Correct 1594 ms 181832 KB Output is correct
45 Correct 1774 ms 186156 KB Output is correct
46 Correct 2069 ms 196648 KB Output is correct
47 Correct 2005 ms 198788 KB Output is correct
48 Correct 1972 ms 198508 KB Output is correct
49 Correct 804 ms 146620 KB Output is correct
50 Correct 733 ms 143608 KB Output is correct
51 Correct 1876 ms 198744 KB Output is correct
52 Correct 811 ms 171716 KB Output is correct
53 Correct 38 ms 85708 KB Output is correct
54 Correct 1761 ms 183824 KB Output is correct
55 Correct 1934 ms 189256 KB Output is correct
56 Correct 2145 ms 193688 KB Output is correct
57 Correct 1256 ms 171176 KB Output is correct
58 Correct 1524 ms 178692 KB Output is correct
59 Correct 1630 ms 191132 KB Output is correct
60 Correct 1332 ms 171220 KB Output is correct
61 Correct 1462 ms 177724 KB Output is correct
62 Correct 866 ms 141504 KB Output is correct
63 Correct 89 ms 91080 KB Output is correct
64 Correct 1164 ms 166412 KB Output is correct
65 Correct 1068 ms 163616 KB Output is correct
66 Correct 757 ms 146940 KB Output is correct
67 Correct 999 ms 158064 KB Output is correct
68 Correct 581 ms 135160 KB Output is correct
69 Correct 2142 ms 194516 KB Output is correct
70 Correct 1762 ms 188340 KB Output is correct
71 Correct 2027 ms 192148 KB Output is correct
72 Correct 789 ms 141972 KB Output is correct
73 Correct 1894 ms 192956 KB Output is correct
74 Correct 708 ms 158832 KB Output is correct
75 Correct 697 ms 150216 KB Output is correct
76 Correct 780 ms 165052 KB Output is correct
77 Correct 903 ms 153904 KB Output is correct
78 Correct 799 ms 148060 KB Output is correct
79 Correct 744 ms 145400 KB Output is correct
80 Correct 672 ms 138148 KB Output is correct
81 Correct 706 ms 162832 KB Output is correct
82 Correct 689 ms 141240 KB Output is correct
83 Correct 733 ms 142380 KB Output is correct
84 Correct 207 ms 105040 KB Output is correct
85 Correct 1848 ms 187404 KB Output is correct
86 Correct 2609 ms 217812 KB Output is correct
87 Correct 104 ms 100112 KB Output is correct
88 Correct 141 ms 97484 KB Output is correct
89 Correct 103 ms 99788 KB Output is correct
90 Correct 65 ms 89548 KB Output is correct
91 Correct 20 ms 81500 KB Output is correct
92 Correct 47 ms 87320 KB Output is correct
93 Correct 607 ms 123284 KB Output is correct
94 Correct 95 ms 91204 KB Output is correct
95 Correct 1307 ms 170432 KB Output is correct
96 Correct 1166 ms 165000 KB Output is correct
97 Correct 942 ms 162432 KB Output is correct
98 Correct 1080 ms 157836 KB Output is correct
99 Correct 3125 ms 257576 KB Output is correct
100 Correct 1966 ms 190660 KB Output is correct
101 Correct 2422 ms 210504 KB Output is correct
102 Correct 854 ms 141836 KB Output is correct
103 Correct 768 ms 162488 KB Output is correct
104 Correct 662 ms 147752 KB Output is correct
105 Correct 751 ms 166096 KB Output is correct
106 Correct 810 ms 169288 KB Output is correct
107 Correct 757 ms 169632 KB Output is correct
108 Correct 82 ms 91336 KB Output is correct
109 Correct 1512 ms 167904 KB Output is correct
110 Correct 1747 ms 190512 KB Output is correct
111 Correct 1595 ms 188856 KB Output is correct
112 Correct 838 ms 154632 KB Output is correct
113 Correct 881 ms 149432 KB Output is correct