Submission #289975

#	Time	Username	Problem	Language	Result	Execution time	Memory
289975		MarcoMeijer	Sky Walking (IOI19_walk)	C++14	33 / 100	325 ms	19036 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e18
#define pb push_back
#define fi first
#define se second
#define sz size()

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
    int n, m;
    n = x.sz; m = l.sz;

    priority_queue<iii> pq;
    map<int,ll> mp;
    RE(i,m) pq.push({r[i],2,i});
    RE(i,m) pq.push({l[i],1,i});
    RE(i,m) pq.push({r[i],0,i});
    vll dp(m);

    ll ans = INF;
    while(!pq.empty()) {
        iii p = pq.top(); pq.pop();
        int x, t, i;
        tie(x, t, i) = p;
        if(t == 2) {
            if(x == n-1) {
                dp[i] = y[i];
            } else {
                dp[i] = INF;
                auto it = mp.lower_bound(y[i]);
                if(it != mp.end())
                    dp[i] = min(dp[i], it->se + it->fi - y[i]);

                it = mp.upper_bound(y[i]);
                if(it != mp.begin())
                    --it, dp[i] = min(dp[i], it->se + y[i] - it->fi);
            }
        } else if(t == 1) {
            if(x == 0)
                ans = min(ans, dp[i]+y[i]);
            mp.erase(y[i]);
        } else {
            mp[y[i]] = dp[i];
        }
    }

    if(ans == INF) ans = -1;
    else ans += x[n-1]-x[0];
	return ans;
}

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