oj.uz

Submission #427645

# Submission time Handle Problem Language Result Execution time Memory
427645 2021-06-14T18:19:28 Z amoo_safar Sky Walking (IOI19_walk) C++17
10 / 100
 37 ms 5956 KB 
#include "walk.h"

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

const int N = 1000 + 10;

int n, m;
vector<int> x, h, l, r, y;

int seg[N << 2];
int Build(int id, int L, int R){
	if(L + 1 == R) return seg[id] = h[L];
	int mid = (L + R) >> 1;
	return seg[id] = max( Build(id << 1, L, mid), Build(id << 1 | 1, mid, R) );
}
int Seg_Get(int id, int l, int r, int L, int R){
	if(r <= L || R <= l) return -1;
	if(l <= L && R <= r) return seg[id];
	int mid = (L + R) >> 1;
	return max( Seg_Get(id << 1, l, r, L, mid), Seg_Get(id << 1 | 1, l, r, mid, R) );
}
int Get_Max(int l, int r){ // [l, r]
	// cerr << ""
	if(r < l) return -1;
	return Seg_Get(1, l, r + 1, 0, n);
}
vector<pii> G[N];
void Add_Edge(int a, int b){
	// cerr << "!! " << a << ' ' << b << '\n';
	int ls = max(l[a], l[b]);
	int rs = min(r[a], r[b]);
	if(max(y[a], y[b]) <= Get_Max(ls, rs)){
		G[a].pb({b, abs(y[a] - y[b])});
		G[b].pb({a, abs(y[a] - y[b])});
	}
	// cerr << "!! " << a << ' ' << b << '\n';
}

vector<int> ins[N], dl[N];
void Add(vector<int> sg){
	for(int i = 0; i < N; i++) ins[i].clear(), dl[i].clear();
	for(int i : sg){
		ins[l[i]].pb(i);
		dl[r[i]].pb(i);
	}
	set< pair<int, int> > st; // y id

	for(int i = 0; i < N; i++){
		// cerr << "^^ " << i << '\n';	
		for(auto u : ins[i]){
			// cerr << "&& " << u << ' ' << y[u] << '\n';
			st.insert({y[u], u});
			auto it = st.find({y[u], u});
			if(it != st.begin())
				Add_Edge(it->S, prev(it) -> S);
			if(next(it) != st.end())
				Add_Edge(it->S, next(it) -> S);
		}
		// cerr << "^^ " << i << '\n';
		for(auto u : dl[i]){
			auto it = st.find({y[u], u});
			if(it != st.begin() && next(it) != st.end())
				Add_Edge(next(it) -> S, prev(it) -> S);
			st.erase(it);
		}
	}
}

ll dis[N];
typedef pair<ll, ll> pll;
ll Djik(int src, int des){
	memset(dis, 31, sizeof dis);
	dis[src] = 0;
	set<pll> st;
	st.insert({dis[src], src});
	while(!st.empty()){
		int fr = st.begin() -> S;
		st.erase(st.begin());
		for(auto [adj, w] : G[fr]){
			assert(w >= 0);
			if(dis[adj] > dis[fr] + w){
				st.erase({dis[adj], adj});
				dis[adj] = dis[fr] + w;
				st.insert({dis[adj], adj});
			}
		}
	}
	return dis[des];
}

int Get_Last(int l, int r, int yy){
	for(int i = r; i >= l; i--)
		if(h[i] >= yy)
			return i;
	return l;
}
int Get_First(int l, int r, int yy){
	for(int i = l; i <= r; i++)
		if(h[i] >= yy)
			return i;
	return r;
}


ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int s, int g) {
	if(s > g) swap(s, g);
	x = _x;
	h = _h;
	n = _x.size();

	ll ans = x[g] - x[s];
	
	vector<int> lft, mid, rgt;
	int u, v;
	for(int i = 0; i < (int) _l.size(); i++){
		u = _l[i];
		v = _r[i];
		int a = -1, b = -1, c = -1;
		if(u <= s){
			a = l.size();
			l.pb(u);
			r.pb(min(s, v));
			y.pb(_y[i]);
		}
		if(s <= v && u <= g){
			b = l.size();
			l.pb(max(u, s));
			r.pb(min(g, v));
			y.pb(_y[i]);
		}
		if(g <= v){
			c = l.size();
			l.pb(max(u, g));
			r.pb(v);
			y.pb(_y[i]);
		}
		if(a != -1) lft.pb(a);
		if(b != -1) mid.pb(b);
		if(c != -1) rgt.pb(c);
		if(a != -1 && b != -1){
			G[a].pb({b, 2 * (x[s] - x[ Get_Last(0, s, _y[i]) ] )});
		}
		
		if(b != -1 && c != -1){
			G[b].pb({c, 2 * (x[ Get_First(g, n - 1, _y[i]) ] - x[g]) });
		}
	}

	l.pb(s); r.pb(s); y.pb(0);
	l.pb(s); r.pb(s); y.pb(0);

	l.pb(g); r.pb(g); y.pb(0);
	l.pb(g); r.pb(g); y.pb(0);
	
	int src = l.size() - 3;
	int des = l.size() - 1;
	
	mid.pb(src - 1);
	lft.pb(src);
	mid.pb(des - 1);
	rgt.pb(des);

	m = l.size();
	

	for(int i = 0; i < m; i++)
		assert(l[i] <= r[i]);
	// for(int i = 0; i < m; i++)
	// 	assert(0 <= l[i]);
	// for(int i = 0; i < m; i++)
	// 	assert(r[i] <= n);
	
	// l = _l;
	// r = _r;
	// y = _y;

	// for(int i = 0; i < m; i++) mid.pb(i);
	Build(1, 0, n);
	// debug("A");
	Add(lft);
	// debug("B");
	Add(mid);
	// debug("C");
	Add(rgt);
	// debug("D");

	ans += Djik(src, des);
	int max_len = 1000000000;
	return ans > 1ll * (n + m) * max_len ? -1 : ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Runtime error 37 ms 5956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 3464 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 3464 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Runtime error 37 ms 5956 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -