oj.uz

Submission #609744

# Submission time Handle Problem Language Result Execution time Memory
609744 2022-07-27T20:21:28 Z leaked Sky Walking (IOI19_walk) C++17
100 / 100
 1959 ms 370880 KB 
#include <bits/stdc++.h>

#include "walk.h"

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()

using namespace std;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,int> pli;

const int N=1e5+1;


struct segtree{
    int t[4*N];
    void build(int v,int tl,int tr,vec<int> &a){
        if(tl==tr){
            t[v]=a[tl];
        }
        else{
            int tm=(tl+tr)>>1;
            build(2*v,tl,tm,a);build(2*v+1,tm+1,tr,a);
            t[v]=max(t[v<<1],t[v<<1|1]);
        }
    }

    int findf(int l,int r,int x,int v,int tl,int tr){
        if(tl>r||tr<l||t[v]<x)
            return -1;
        if(tl==tr)
            return tl;
        int tm=(tl+tr)>>1;
        int j=findf(l,r,x,2*v,tl,tm);
        if(j==-1) j=findf(l,r,x,2*v+1,tm+1,tr);
        return j;
    }
    int findl(int l,int r,int x,int v,int tl,int tr){
        if(tl>r||tr<l||t[v]<x)
            return -1;
        if(tl==tr)
            return tl;
        int tm=(tl+tr)>>1;
        int j=findl(l,r,x,2*v+1,tm+1,tr);
        if(j==-1) j=findl(l,r,x,2*v,tl,tm);
        return j;
    }
}sega;


int n;

vec<array<int,3>> process(vec<array<int,3>> arr,int p){

    vec<array<int,3>> wi;

    for(auto &z : arr){
        auto [l,r,h] = z;
        int l1=l,r1=r;

        l=sega.findf(l,r,h,1,0,n-1);
        r=sega.findl(l,r,h,1,0,n-1);

        if(l==-1) l=r1+1;
        if(r==-1) r=l1-1;

        if(l>r) continue;

        if(l<=p && r>=p){
            int a=sega.findl(l,p,h,1,0,n-1);
            int b=sega.findf(p,r,h,1,0,n-1);
            assert(a!=-1 && b!=-1);

            wi.pb({l,a,h});
            wi.pb({a,b,h});
            wi.pb({b,r,h});

        }
        else{
            wi.pb({l,r,h});
        }
    }

    return wi;
}

const int NT=2e6+1;

vec<pii> g[2*NT];

map<int,int> cords[N];
set<pii> pos[NT];

int tt=0;
int getid(int i,int j){
//    cout<<"I "<<i<<' '<<j<<endl;
    if(!cords[i].count(j)){
        cords[i][j]=tt++;
        pos[j].insert({i,cords[i][j]});
    }
    return cords[i][j];
}
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 gt){

    n=sz(x);
    sega.build(1,0,n-1,h);

    vec<array<int,3>> arr;
    int m=sz(l);
    for(int i=0;i<m;i++) arr.pb({l[i],r[i],y[i]});


    arr=process(arr,s);
    arr=process(arr,gt);

    sort(all(arr));
    arr.erase(unique(all(arr)),arr.end());

    sort(all(arr),[&](array<int,3> f,array<int,3> s){
        return f[2]<s[2];
    });

////    for(auto &z : arr)
////        cout<<z[0]<<' '<<z[1]<<' '<<z[2]<<endl;
////    exit(0);

    m=sz(arr);

    vec<vec<int>> adds(n,vec<int>());
    vec<vec<int>> dels(n,vec<int>());

    for(int i=0;i<m;i++){
        adds[arr[i][0]].pb(i);
        dels[arr[i][1]].pb(i);
    }

    set<int> st;

    for(int i=0;i<n;i++){


        for(auto &z : adds[i]){
            auto it=st.lower_bound(z);
            getid(i,z);

            if(it!=st.begin()){
                int c=*prev(it);

                getid(i,c);


                int v=getid(i,c),u=getid(i,z),w=abs(arr[c][2]-arr[z][2]);
                g[v].pb({u,w});
                g[u].pb({v,w});
            }
        }

        for(auto &z : adds[i]){
            st.insert(z);
        }

        for(auto &z : dels[i]){
            st.erase(z);
        }


        for(auto &z : dels[i]){
            auto it=st.lower_bound(z);
            getid(i,z);

            if(it!=st.begin()){
                int c=*prev(it);
                getid(i,c);
            }
        }



    }

    int fi=tt++,si=tt++;

    for(auto &z : cords[s]){
        g[fi].pb({z.s,arr[z.f][2]});
    }
    for(auto &z : cords[gt]){
//        cout<<"SHIS "<<z.s<<' '<<arr[z.f][2]<<endl;
        g[z.s].pb({si,arr[z.f][2]});
    }

    for(int i=0;i<m;i++){
        pii last=m_p(-1,-1);
        for(auto z : pos[i]){
            if(last.f!=-1){
                int v=last.s,u=z.s,w=abs(x[z.f]-x[last.f]);


                g[v].pb({u,w});
                g[u].pb({v,w});

            }
            last=z;
        }
    }

    for(int i=0;i<n;i++){
        pii last=m_p(-1,-1);
        for(auto &z : cords[i]){
            if(last.f!=-1){
                int v=last.s,u=z.s,w=abs(arr[z.f][2]-arr[last.f][2]);

                g[v].pb({u,w});
                g[u].pb({v,w});
            }
            last=z;
        }
    }

    const ll inf=1e18;

    vec<ll> dst(tt,inf);

    priority_queue<pli,vec<pli>,greater<pli>> pq;

    dst[fi]=0;
    pq.push({dst[fi],fi});

    while(!pq.empty()){
        auto [d,v]=pq.top();pq.pop();
//        cout<<"PQ "<<d<<' '<<v<<endl;
        if(dst[v]!=d) continue;
        for(auto &z : g[v]){
            if(umin(dst[z.f],d+z.s)){
                pq.push({dst[z.f],z.f});
            }
        }
    }

    if(dst[si]==inf) dst[si]=-1;

    return dst[si];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 192972 KB Output is correct
2 Correct 82 ms 192776 KB Output is correct
3 Correct 85 ms 192872 KB Output is correct
4 Correct 92 ms 192860 KB Output is correct
5 Correct 86 ms 192852 KB Output is correct
6 Correct 86 ms 192936 KB Output is correct
7 Correct 86 ms 192852 KB Output is correct
8 Correct 96 ms 192848 KB Output is correct
9 Correct 85 ms 192772 KB Output is correct
10 Correct 87 ms 192856 KB Output is correct
11 Correct 83 ms 192804 KB Output is correct
12 Correct 84 ms 192832 KB Output is correct
13 Correct 86 ms 192880 KB Output is correct
14 Correct 85 ms 192808 KB Output is correct
15 Correct 84 ms 192904 KB Output is correct
16 Correct 94 ms 192844 KB Output is correct
17 Correct 85 ms 192840 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 192860 KB Output is correct
2 Correct 85 ms 192816 KB Output is correct
3 Correct 583 ms 254808 KB Output is correct
4 Correct 551 ms 265708 KB Output is correct
5 Correct 388 ms 248700 KB Output is correct
6 Correct 406 ms 248912 KB Output is correct
7 Correct 389 ms 248796 KB Output is correct
8 Correct 627 ms 257700 KB Output is correct
9 Correct 532 ms 259632 KB Output is correct
10 Correct 584 ms 265704 KB Output is correct
11 Correct 476 ms 248776 KB Output is correct
12 Correct 398 ms 243908 KB Output is correct
13 Correct 562 ms 269928 KB Output is correct
14 Correct 502 ms 254764 KB Output is correct
15 Correct 490 ms 257600 KB Output is correct
16 Correct 350 ms 245064 KB Output is correct
17 Correct 348 ms 241868 KB Output is correct
18 Correct 976 ms 285992 KB Output is correct
19 Correct 102 ms 196600 KB Output is correct
20 Correct 346 ms 231632 KB Output is correct
21 Correct 349 ms 240984 KB Output is correct
22 Correct 312 ms 241872 KB Output is correct
23 Correct 552 ms 260888 KB Output is correct
24 Correct 341 ms 242304 KB Output is correct
25 Correct 344 ms 241864 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 213780 KB Output is correct
2 Correct 644 ms 263668 KB Output is correct
3 Correct 731 ms 266204 KB Output is correct
4 Correct 776 ms 276532 KB Output is correct
5 Correct 884 ms 277520 KB Output is correct
6 Correct 875 ms 279032 KB Output is correct
7 Correct 398 ms 239828 KB Output is correct
8 Correct 379 ms 243748 KB Output is correct
9 Correct 969 ms 282912 KB Output is correct
10 Correct 398 ms 247832 KB Output is correct
11 Correct 97 ms 197232 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 213780 KB Output is correct
2 Correct 644 ms 263668 KB Output is correct
3 Correct 731 ms 266204 KB Output is correct
4 Correct 776 ms 276532 KB Output is correct
5 Correct 884 ms 277520 KB Output is correct
6 Correct 875 ms 279032 KB Output is correct
7 Correct 398 ms 239828 KB Output is correct
8 Correct 379 ms 243748 KB Output is correct
9 Correct 969 ms 282912 KB Output is correct
10 Correct 398 ms 247832 KB Output is correct
11 Correct 97 ms 197232 KB Output is correct
12 Correct 688 ms 266124 KB Output is correct
13 Correct 639 ms 275628 KB Output is correct
14 Correct 867 ms 277380 KB Output is correct
15 Correct 619 ms 265232 KB Output is correct
16 Correct 606 ms 265288 KB Output is correct
17 Correct 670 ms 275132 KB Output is correct
18 Correct 598 ms 265188 KB Output is correct
19 Correct 589 ms 265512 KB Output is correct
20 Correct 397 ms 239568 KB Output is correct
21 Correct 115 ms 202872 KB Output is correct
22 Correct 465 ms 259732 KB Output is correct
23 Correct 481 ms 257816 KB Output is correct
24 Correct 376 ms 244340 KB Output is correct
25 Correct 406 ms 253108 KB Output is correct
26 Correct 313 ms 236404 KB Output is correct
27 Correct 888 ms 277652 KB Output is correct
28 Correct 583 ms 275100 KB Output is correct
29 Correct 904 ms 278672 KB Output is correct
30 Correct 405 ms 239908 KB Output is correct
31 Correct 926 ms 282804 KB Output is correct
32 Correct 392 ms 243548 KB Output is correct
33 Correct 333 ms 241904 KB Output is correct
34 Correct 439 ms 250784 KB Output is correct
35 Correct 393 ms 249208 KB Output is correct
36 Correct 386 ms 244324 KB Output is correct
37 Correct 345 ms 240960 KB Output is correct
38 Correct 337 ms 241884 KB Output is correct
39 Correct 514 ms 260904 KB Output is correct
40 Correct 345 ms 242288 KB Output is correct
41 Correct 341 ms 241864 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 192972 KB Output is correct
2 Correct 82 ms 192776 KB Output is correct
3 Correct 85 ms 192872 KB Output is correct
4 Correct 92 ms 192860 KB Output is correct
5 Correct 86 ms 192852 KB Output is correct
6 Correct 86 ms 192936 KB Output is correct
7 Correct 86 ms 192852 KB Output is correct
8 Correct 96 ms 192848 KB Output is correct
9 Correct 85 ms 192772 KB Output is correct
10 Correct 87 ms 192856 KB Output is correct
11 Correct 83 ms 192804 KB Output is correct
12 Correct 84 ms 192832 KB Output is correct
13 Correct 86 ms 192880 KB Output is correct
14 Correct 85 ms 192808 KB Output is correct
15 Correct 84 ms 192904 KB Output is correct
16 Correct 94 ms 192844 KB Output is correct
17 Correct 85 ms 192840 KB Output is correct
18 Correct 83 ms 192860 KB Output is correct
19 Correct 85 ms 192816 KB Output is correct
20 Correct 583 ms 254808 KB Output is correct
21 Correct 551 ms 265708 KB Output is correct
22 Correct 388 ms 248700 KB Output is correct
23 Correct 406 ms 248912 KB Output is correct
24 Correct 389 ms 248796 KB Output is correct
25 Correct 627 ms 257700 KB Output is correct
26 Correct 532 ms 259632 KB Output is correct
27 Correct 584 ms 265704 KB Output is correct
28 Correct 476 ms 248776 KB Output is correct
29 Correct 398 ms 243908 KB Output is correct
30 Correct 562 ms 269928 KB Output is correct
31 Correct 502 ms 254764 KB Output is correct
32 Correct 490 ms 257600 KB Output is correct
33 Correct 350 ms 245064 KB Output is correct
34 Correct 348 ms 241868 KB Output is correct
35 Correct 976 ms 285992 KB Output is correct
36 Correct 102 ms 196600 KB Output is correct
37 Correct 346 ms 231632 KB Output is correct
38 Correct 349 ms 240984 KB Output is correct
39 Correct 312 ms 241872 KB Output is correct
40 Correct 552 ms 260888 KB Output is correct
41 Correct 341 ms 242304 KB Output is correct
42 Correct 344 ms 241864 KB Output is correct
43 Correct 219 ms 213780 KB Output is correct
44 Correct 644 ms 263668 KB Output is correct
45 Correct 731 ms 266204 KB Output is correct
46 Correct 776 ms 276532 KB Output is correct
47 Correct 884 ms 277520 KB Output is correct
48 Correct 875 ms 279032 KB Output is correct
49 Correct 398 ms 239828 KB Output is correct
50 Correct 379 ms 243748 KB Output is correct
51 Correct 969 ms 282912 KB Output is correct
52 Correct 398 ms 247832 KB Output is correct
53 Correct 97 ms 197232 KB Output is correct
54 Correct 688 ms 266124 KB Output is correct
55 Correct 639 ms 275628 KB Output is correct
56 Correct 867 ms 277380 KB Output is correct
57 Correct 619 ms 265232 KB Output is correct
58 Correct 606 ms 265288 KB Output is correct
59 Correct 670 ms 275132 KB Output is correct
60 Correct 598 ms 265188 KB Output is correct
61 Correct 589 ms 265512 KB Output is correct
62 Correct 397 ms 239568 KB Output is correct
63 Correct 115 ms 202872 KB Output is correct
64 Correct 465 ms 259732 KB Output is correct
65 Correct 481 ms 257816 KB Output is correct
66 Correct 376 ms 244340 KB Output is correct
67 Correct 406 ms 253108 KB Output is correct
68 Correct 313 ms 236404 KB Output is correct
69 Correct 888 ms 277652 KB Output is correct
70 Correct 583 ms 275100 KB Output is correct
71 Correct 904 ms 278672 KB Output is correct
72 Correct 405 ms 239908 KB Output is correct
73 Correct 926 ms 282804 KB Output is correct
74 Correct 392 ms 243548 KB Output is correct
75 Correct 333 ms 241904 KB Output is correct
76 Correct 439 ms 250784 KB Output is correct
77 Correct 393 ms 249208 KB Output is correct
78 Correct 386 ms 244324 KB Output is correct
79 Correct 345 ms 240960 KB Output is correct
80 Correct 337 ms 241884 KB Output is correct
81 Correct 514 ms 260904 KB Output is correct
82 Correct 345 ms 242288 KB Output is correct
83 Correct 341 ms 241864 KB Output is correct
84 Correct 195 ms 209620 KB Output is correct
85 Correct 807 ms 272720 KB Output is correct
86 Correct 1415 ms 321472 KB Output is correct
87 Correct 141 ms 208240 KB Output is correct
88 Correct 138 ms 208140 KB Output is correct
89 Correct 143 ms 208224 KB Output is correct
90 Correct 108 ms 198764 KB Output is correct
91 Correct 86 ms 192968 KB Output is correct
92 Correct 105 ms 196512 KB Output is correct
93 Correct 326 ms 228844 KB Output is correct
94 Correct 120 ms 203492 KB Output is correct
95 Correct 480 ms 262944 KB Output is correct
96 Correct 513 ms 258920 KB Output is correct
97 Correct 436 ms 251764 KB Output is correct
98 Correct 421 ms 253104 KB Output is correct
99 Correct 1959 ms 370880 KB Output is correct
100 Correct 828 ms 277064 KB Output is correct
101 Correct 1255 ms 310200 KB Output is correct
102 Correct 393 ms 240472 KB Output is correct
103 Correct 405 ms 243688 KB Output is correct
104 Correct 335 ms 241748 KB Output is correct
105 Correct 450 ms 251848 KB Output is correct
106 Correct 439 ms 252836 KB Output is correct
107 Correct 496 ms 260228 KB Output is correct
108 Correct 125 ms 199740 KB Output is correct
109 Correct 678 ms 262436 KB Output is correct
110 Correct 590 ms 274668 KB Output is correct
111 Correct 565 ms 275348 KB Output is correct
112 Correct 401 ms 249032 KB Output is correct
113 Correct 400 ms 247484 KB Output is correct