Submission #1026103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026103		hotboy2703	Sky Walking (IOI19_walk)	C++17	33 / 100	147 ms	21184 KiB

walk

#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))
//namespace fail{

    struct walk{
        ll l,r,y;
    };
    vector <walk> all;
    const ll MAXN = 1e5 + 100;
    const ll INF = 1e18;
    ll dp[MAXN];
    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;
    //    {
    //        set <ll> s;
    //        s.insert(-1);
    //        s.insert(n);
    //        for (ll i = 0,ptr = 0;i < n;i ++){
    //            while (ptr < sz(order) && h[order[ptr]] >= all[i].y){
    //                s.insert(order[ptr]);
    //                ptr++;
    //            }
    //            all[i].l = *lower_bound(s.begin(),s.end(),all[i].l);
    //            all[i].r = *prev(upper_bound(s.begin(),s.end(),all[i].r));
    //        }
    //    }
        sort(all.begin(),all.end(),[](walk a1,walk a2){return a1.r<a2.r;});
        vector <pll> event;
        for (ll i = 0;i < m;i ++){
            if (all[i].l > all[i].r)continue;
            event.push_back(MP(all[i].l,i));
            event.push_back(MP(all[i].r,i));
        }
    //    cout<<"OK"<<endl;
        sort(event.begin(),event.end());
        memset(dp,0x3f,sizeof dp);
        set <pll> s;
    //    return -1;
        ll res = INF;
        for (ll i = 0,ptr = 0;i < m;i ++){
    //        cout<<i<<endl;
            if (all[i].l > all[i].r)continue;
            while (ptr < sz(event) && event[ptr].fi <= all[i].r){
                pll x;
                x.se = event[ptr].se;
                x.fi = all[x.se].y;
                if (s.find(x) != s.end())s.erase(x);
                else s.insert(x);
    //    cout<<ptr<<endl;
                ptr++;
            }

            if (all[i].l == 0)dp[i] = all[i].y;
            auto tmp = s.lower_bound(MP(all[i].y,i));
            if (tmp != s.begin())dp[(*prev(tmp)).se] = min(dp[(*prev(tmp)).se],dp[i] + abs((*prev(tmp)).fi - all[i].y));
    //        assert(tmp != s.end());
            if (tmp != s.end())dp[(*tmp).se] = min(dp[(*tmp).se],dp[i] + abs((*tmp).fi - all[i].y));
            if (all[i].r == n - 1)res = min(res,dp[i] + x[n-1]-x[0]+all[i].y);
//            cout<<i<<' '<<all[i].l<<' '<<all[i].r<<' '<<dp[i]<<endl;
        }
        if (res==INF)res=-1;
        return res;
    }

//}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43