oj.uz

Submission #602263

# Submission time Handle Problem Language Result Execution time Memory
602263 2022-07-22T19:30:46 Z leaked Sky Walking (IOI19_walk) C++17
25 / 100
 924 ms 98484 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;
typedef pair<int,int> pii;
typedef long long ll;
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);}

const int N=1e5+1;
const ll inf=1e18;

map<int,ll> dp[N];
int y[N];

struct setik{
    map<pii,ll> dp;

    void upd(pii i,ll x){
        dp[i]=x;
        auto it=dp.lower_bound(i);
        if(it!=dp.begin() && prev(it)->s>dp[i])
            upd(prev(it)->f,x);
    }
    void getval(pii i,int yt){
//        cout<<"W "<<i.f<<' '<<i.s<<endl;
        dp[i]=inf;
        auto it=dp.lower_bound(i);
        ll vl=inf;
        if(next(it)!=dp.end() && y[next(it)->f.s]<=yt)
            umin(vl,next(it)->s);
        if(it!=dp.begin()){
//            cout<<prev(it)->f.s<<' '<<i.
            umin(vl,2*abs(y[prev(it)->f.s]-y[i.s])+prev(it)->s);
        }
        upd(i,vl);
    }
}_dp;
vec<pii> scan[N];
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){

    set<int> st;
    int n=sz(x);
    int m=sz(l);
    {
        vec<int> p(m);
        for(int i=0;i<m;i++) p[i]=i;
        sort(all(p),[&](int i,int j){return y[i]<y[j];});
        vec<int> nl(m),nr(m),ny(m);
        for(int i=0;i<m;i++)
            nl[i]=l[p[i]],nr[i]=r[p[i]],ny[i]=y[p[i]];
        swap(l,nl);swap(r,nr);swap(y,ny);
//        for(auto &z : y)
//            cout<<z<<' ';
//        cout<<endl;
    }
//    y.pb(0);
//    l.pb(n),r.pb(-1);

    {
        vec<array<int,3>> haha;
        st.insert(-1);
        st.insert(n);
        for(int i=0;i<n;i++) haha.pb({h[i],1,i});
        for(int i=0;i<m;i++) haha.pb({y[i],0,i});
        sort(rall(haha));
        for(auto &z : haha){
            if(z[1]==0){
                l[z[2]]=*st.lower_bound(l[z[2]]);
                r[z[2]]=*prev(st.upper_bound(r[z[2]]));
            }
            else{
                st.insert(z[2]);
            }
        }
        st.clear();
    }
    for(int i=0;i<m;i++){
        if(l[i]>r[i]) continue;
        scan[l[i]].pb({i,1});
        scan[r[i]+1].pb({i,-1});
        ::y[i]=y[i];
    }
    if(s==0 && g==n-1){
        for(auto &z : scan[0]){
            _dp.upd(m_p(y[z.f],z.f),2*y[z.f]);
        }
        for(int i=1;i<n;i++){
            for(auto &z : scan[i]){
                if(z.s==-1){
//                    cout<<"DEL "<<z.f<endl;
                    _dp.dp.erase(m_p(y[z.f],z.f));
                }
            }
            auto it=_dp.dp.upper_bound(m_p(h[i-1],1e9));
            if(it!=_dp.dp.end() && it->f.f<=h[i]){
                auto itj=_dp.dp.upper_bound(m_p(h[i],-1));
                --itj;
                if(itj->s!=inf){
                    while(it->s==inf) ++it;
                    _dp.upd(it->f,it->s);
                }
            }
            for(auto &z : scan[i]){
                if(z.s==-1) continue;
                _dp.getval(m_p(y[z.f],z.f),h[i]);
            }
//            cout<<i<<endl;
//            for(auto &q : _dp.dp)
//                cout<<q.f<<' '<<q.s<<endl;
//            cout<<endl;
        }
        ll mn=inf;
        for(auto &z : _dp.dp)
            umin(mn,z.s+x[n-1]-x[0]);
        if(mn==inf)
            mn=-1;
        return mn;
    }

    vec<vec<int>> ids(m,vec<int>());
    for(int i=0;i<n;i++){
        dp[i][-1]=inf;
        for(auto &z : scan[i]){
            if(z.s==-1)
                st.erase(z.f);
            else
                st.insert(z.f);
        }
        for(auto z : st){
            if(y[z]>h[i]) break;
//            cout<<"I "<<i<<' '<<z<<endl;
            dp[i][z]=inf;
            ids[z].pb(i);
        }
    }

    priority_queue<array<ll,3>,vec<array<ll,3>>,greater<array<ll,3>>> pq;
    pq.push({0,s,-1});
    dp[s][-1]=0;
    while(!pq.empty()){
        auto [xt,v,j]=pq.top();pq.pop();
        if(dp[v][j]!=xt) continue;
//        cout<<v<<' '<<j<<' '<<dp[v][j]<<endl;
        auto getnxt=[&](int v,int j){
            if(j==-1)
                return n;
            int w=lower_bound(all(ids[j]),v)-ids[j].begin();
            if(w==sz(ids[j])-1)
                return n;
            return ids[j][w+1];
        };
        auto getprv=[&](int v,int j){
            if(j==-1)
                return -1;
            int w=lower_bound(all(ids[j]),v)-ids[j].begin();
            if(w==0)
                return -1;
            return ids[j][w-1];
        };

        int f=getnxt(v,j),s=getprv(v,j);

        for(auto &z : {f,s}){
            if(z==n || z==-1)
                continue;
            if(umin(dp[z][j],xt+abs(x[z]-x[v])))
                pq.push({dp[z][j],z,j});
        }
//        assert(dp[v].count(j));
        auto it=dp[v].find(j);
//        cout<<next(it)->f<<endl;
        if(next(it)!=dp[v].end()){
            int nj=next(it)->f;
            int r=abs((nj==-1?0:y[nj])-(j==-1?0:y[j]));
            if(umin(dp[v][nj],xt+r))
                pq.push({dp[v][nj],v,nj});
        }
        if(it!=dp[v].begin()){
            int nj=prev(it)->f;
            int r=abs((nj==-1?0:y[nj])-(j==-1?0:y[j]));
            if(umin(dp[v][nj],xt+r))
                pq.push({dp[v][nj],v,nj});
        }
    }
    if(dp[g][-1]==inf)
        dp[g][-1]=-1;
    return dp[g][-1];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7352 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 6 ms 7380 KB Output is correct
7 Correct 4 ms 7356 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7356 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7352 KB Output is correct
12 Correct 4 ms 7356 KB Output is correct
13 Correct 4 ms 7252 KB Output is correct
14 Correct 4 ms 7352 KB Output is correct
15 Correct 4 ms 7356 KB Output is correct
16 Correct 5 ms 7252 KB Output is correct
17 Correct 5 ms 7252 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 700 ms 66996 KB Output is correct
4 Correct 579 ms 77012 KB Output is correct
5 Correct 252 ms 67212 KB Output is correct
6 Correct 263 ms 62236 KB Output is correct
7 Correct 251 ms 67324 KB Output is correct
8 Correct 924 ms 81124 KB Output is correct
9 Correct 346 ms 67956 KB Output is correct
10 Correct 727 ms 98484 KB Output is correct
11 Correct 318 ms 46516 KB Output is correct
12 Correct 194 ms 22312 KB Output is correct
13 Incorrect 201 ms 22248 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 10964 KB Output is correct
2 Correct 138 ms 14228 KB Output is correct
3 Correct 166 ms 15104 KB Output is correct
4 Correct 284 ms 22308 KB Output is correct
5 Correct 294 ms 25188 KB Output is correct
6 Correct 321 ms 22356 KB Output is correct
7 Correct 146 ms 19592 KB Output is correct
8 Correct 192 ms 22292 KB Output is correct
9 Correct 288 ms 22392 KB Output is correct
10 Correct 198 ms 21644 KB Output is correct
11 Correct 37 ms 11756 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 10964 KB Output is correct
2 Correct 138 ms 14228 KB Output is correct
3 Correct 166 ms 15104 KB Output is correct
4 Correct 284 ms 22308 KB Output is correct
5 Correct 294 ms 25188 KB Output is correct
6 Correct 321 ms 22356 KB Output is correct
7 Correct 146 ms 19592 KB Output is correct
8 Correct 192 ms 22292 KB Output is correct
9 Correct 288 ms 22392 KB Output is correct
10 Correct 198 ms 21644 KB Output is correct
11 Correct 37 ms 11756 KB Output is correct
12 Correct 164 ms 15132 KB Output is correct
13 Correct 258 ms 22288 KB Output is correct
14 Correct 347 ms 25144 KB Output is correct
15 Correct 204 ms 22104 KB Output is correct
16 Correct 244 ms 22312 KB Output is correct
17 Correct 238 ms 22316 KB Output is correct
18 Correct 202 ms 22180 KB Output is correct
19 Correct 270 ms 22268 KB Output is correct
20 Correct 169 ms 19480 KB Output is correct
21 Correct 75 ms 16692 KB Output is correct
22 Correct 174 ms 21376 KB Output is correct
23 Correct 174 ms 21632 KB Output is correct
24 Correct 184 ms 22020 KB Output is correct
25 Correct 155 ms 21384 KB Output is correct
26 Correct 203 ms 26812 KB Output is correct
27 Correct 310 ms 24412 KB Output is correct
28 Correct 239 ms 22284 KB Output is correct
29 Correct 287 ms 22312 KB Output is correct
30 Correct 188 ms 19484 KB Output is correct
31 Correct 289 ms 22504 KB Output is correct
32 Correct 142 ms 20400 KB Output is correct
33 Correct 172 ms 21528 KB Output is correct
34 Correct 161 ms 21412 KB Output is correct
35 Correct 168 ms 21128 KB Output is correct
36 Incorrect 148 ms 20640 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7352 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 6 ms 7380 KB Output is correct
7 Correct 4 ms 7356 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7356 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7352 KB Output is correct
12 Correct 4 ms 7356 KB Output is correct
13 Correct 4 ms 7252 KB Output is correct
14 Correct 4 ms 7352 KB Output is correct
15 Correct 4 ms 7356 KB Output is correct
16 Correct 5 ms 7252 KB Output is correct
17 Correct 5 ms 7252 KB Output is correct
18 Correct 5 ms 7252 KB Output is correct
19 Correct 4 ms 7252 KB Output is correct
20 Correct 700 ms 66996 KB Output is correct
21 Correct 579 ms 77012 KB Output is correct
22 Correct 252 ms 67212 KB Output is correct
23 Correct 263 ms 62236 KB Output is correct
24 Correct 251 ms 67324 KB Output is correct
25 Correct 924 ms 81124 KB Output is correct
26 Correct 346 ms 67956 KB Output is correct
27 Correct 727 ms 98484 KB Output is correct
28 Correct 318 ms 46516 KB Output is correct
29 Correct 194 ms 22312 KB Output is correct
30 Incorrect 201 ms 22248 KB Output isn't correct
31 Halted 0 ms 0 KB -