Submission #296179

#	Time	Username	Problem	Language	Result	Execution time	Memory
296179		Noam13	Sky Walking (IOI19_walk)	C++14	15 / 100	1260 ms	549112 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define int int64_t
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define ii pair<int, int>
#define vii vector<ii>
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define chkmin(a,b) a = min(a,b)
using namespace std;
const int INF = 2e18;
struct SEG{
	int l,r,mid;
	multiset<int> vs;
	int vp = INF, vm = INF;
	SEG *lp=0, *rp=0;
	SEG(int l, int r): l(l), r(r), mid((l+r)/2){
		if (l+1==r) vs.insert(INF);
	}
	void fix(){
		if (!lp) lp = new SEG(l, mid);
		if (!rp) rp = new SEG(mid, r);
		vp = min(lp->vp, rp->vp);
		vm = min(lp->vm, rp->vm);
	}
	void update(int i, int v, bool in){
		if (l+1==r){
			if (in){
				vs.insert(v);
			}
			else{
				vs.erase(vs.find(v));
			}
			int vv = *vs.begin();
			vp = vv + l;
			vm = vv - l;
			return ;
		}
		fix();
		if (i<mid) lp->update(i, v, in);
		else rp->update(i, v, in);
		fix();
	}
	int query(int a, int b, bool plus){
		if (a>=r || b<=l) return INF;
		if (a<=l && r<=b) return (plus?vp:vm);
		fix();
		return min(lp->query(a,b,plus), rp->query(a,b,plus));
	}
};
long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g) {
	int n = x.size(), m = l.size();
	vvi in(n), out(n);
	loop(i,0,m){
		in[l[i]].pb(i);
		out[r[i]].pb(i);
	}
	SEG seg(0, 2e9);
	seg.update(0,-x[0],1);
	vi vals(m);
	int ans;
	loop(pos,0,n){
		for(auto i:in[pos]){
			int v  = INF;
			chkmin(v, y[i] + seg.query(0, y[i], 0));
			chkmin(v, seg.query(y[i], h[pos]+1, 1) - y[i]);
			//v+=x[pos];
			vals[i] = v;
			//vals.pb({y[i], v});
			seg.update(y[i], vals[i], 1);
		}
		ans = seg.query(0, h[pos]+1, 1) + x[pos];
		for(auto i:out[pos]){
			seg.update(y[i], vals[i], 0);
		}
		if (pos==0){
			seg.update(0, -x[0],0);
		}
	}
	if (ans>INF/2) ans = -1;
	return ans;
}
/*
clear
g++ grader.cpp walk.cpp -o a ; ./a
7 5
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
2 3 1
3 4 2
4 6 5
0 6

2 1
0 2
1 2
0 1 2
0 1
*/

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int32_t, int32_t)':
walk.cpp:84:2: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |  if (ans>INF/2) ans = -1;
      |  ^~

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