Submission #1025927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025927		hotboy2703	Sky Walking (IOI19_walk)	C++17	0 / 100	4038 ms	4712 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))
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 < n;i ++){
        if (all[i].l > all[i].r)continue;
        event.push_back(MP(all[i].l,i));
        event.push_back(MP(all[i].r+1,i));
    }
//    cout<<"OK"<<endl;
    sort(event.begin(),event.end());
    memset(dp,0x3f,sizeof dp);
    set <pll> s;
    ll res = 1e18;
    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++;
        }
//        cout<<i<<' '<<dp[i]<<endl;
        if (all[i].l == 0)dp[i] = all[i].y;
        auto tmp = s.find(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));
        if (next(tmp) != s.end())dp[(*next(tmp)).se] = min(dp[(*next(tmp)).se],dp[i] + abs((*next(tmp)).fi - all[i].y));
        if (all[i].r == n - 1)res = min(res,dp[i] + x[n-1]-x[0]+all[i].y);
    }
    if (res==INF)res=-1;
    return res;
}

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