oj.uz

Submission #427648

# Submission time Handle Problem Language Result Execution time Memory
427648 2021-06-14T18:20:03 Z amoo_safar Sky Walking (IOI19_walk) C++17
43 / 100
 1755 ms 51488 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 = 3e5 + 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 20 ms 23748 KB Output is correct
2 Correct 20 ms 23768 KB Output is correct
3 Correct 20 ms 23748 KB Output is correct
4 Correct 20 ms 23676 KB Output is correct
5 Correct 20 ms 23748 KB Output is correct
6 Correct 20 ms 23736 KB Output is correct
7 Correct 20 ms 23756 KB Output is correct
8 Correct 21 ms 23752 KB Output is correct
9 Correct 20 ms 23748 KB Output is correct
10 Correct 21 ms 23760 KB Output is correct
11 Correct 20 ms 23744 KB Output is correct
12 Correct 20 ms 23752 KB Output is correct
13 Correct 20 ms 23756 KB Output is correct
14 Correct 20 ms 23748 KB Output is correct
15 Correct 20 ms 23752 KB Output is correct
16 Correct 23 ms 23708 KB Output is correct
17 Correct 21 ms 23760 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23764 KB Output is correct
2 Correct 26 ms 23736 KB Output is correct
3 Correct 334 ms 37208 KB Output is correct
4 Correct 316 ms 47212 KB Output is correct
5 Correct 236 ms 41768 KB Output is correct
6 Correct 479 ms 42316 KB Output is correct
7 Correct 204 ms 41728 KB Output is correct
8 Correct 261 ms 39460 KB Output is correct
9 Correct 269 ms 44904 KB Output is correct
10 Correct 294 ms 46228 KB Output is correct
11 Correct 336 ms 41628 KB Output is correct
12 Correct 197 ms 44452 KB Output is correct
13 Correct 342 ms 48168 KB Output is correct
14 Correct 1755 ms 47468 KB Output is correct
15 Incorrect 642 ms 46048 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 30972 KB Output is correct
2 Correct 329 ms 36852 KB Output is correct
3 Correct 331 ms 37408 KB Output is correct
4 Correct 481 ms 42892 KB Output is correct
5 Correct 652 ms 44184 KB Output is correct
6 Correct 685 ms 46748 KB Output is correct
7 Correct 216 ms 36048 KB Output is correct
8 Correct 256 ms 40388 KB Output is correct
9 Correct 877 ms 51372 KB Output is correct
10 Correct 393 ms 47864 KB Output is correct
11 Correct 33 ms 25436 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 30972 KB Output is correct
2 Correct 329 ms 36852 KB Output is correct
3 Correct 331 ms 37408 KB Output is correct
4 Correct 481 ms 42892 KB Output is correct
5 Correct 652 ms 44184 KB Output is correct
6 Correct 685 ms 46748 KB Output is correct
7 Correct 216 ms 36048 KB Output is correct
8 Correct 256 ms 40388 KB Output is correct
9 Correct 877 ms 51372 KB Output is correct
10 Correct 393 ms 47864 KB Output is correct
11 Correct 33 ms 25436 KB Output is correct
12 Correct 358 ms 37408 KB Output is correct
13 Correct 409 ms 42880 KB Output is correct
14 Correct 585 ms 44064 KB Output is correct
15 Correct 385 ms 42032 KB Output is correct
16 Correct 427 ms 45828 KB Output is correct
17 Correct 488 ms 43684 KB Output is correct
18 Correct 405 ms 41968 KB Output is correct
19 Correct 453 ms 45792 KB Output is correct
20 Correct 242 ms 36164 KB Output is correct
21 Correct 56 ms 27332 KB Output is correct
22 Correct 332 ms 39372 KB Output is correct
23 Correct 256 ms 39144 KB Output is correct
24 Correct 225 ms 37924 KB Output is correct
25 Correct 216 ms 38880 KB Output is correct
26 Correct 214 ms 38324 KB Output is correct
27 Correct 671 ms 44536 KB Output is correct
28 Correct 358 ms 42628 KB Output is correct
29 Correct 691 ms 46864 KB Output is correct
30 Correct 232 ms 36000 KB Output is correct
31 Correct 837 ms 51488 KB Output is correct
32 Correct 318 ms 43668 KB Output is correct
33 Correct 325 ms 42800 KB Output is correct
34 Correct 398 ms 46744 KB Output is correct
35 Correct 312 ms 41856 KB Output is correct
36 Correct 221 ms 40312 KB Output is correct
37 Correct 212 ms 39820 KB Output is correct
38 Correct 235 ms 40468 KB Output is correct
39 Correct 555 ms 49740 KB Output is correct
40 Correct 271 ms 40444 KB Output is correct
41 Correct 211 ms 40004 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23748 KB Output is correct
2 Correct 20 ms 23768 KB Output is correct
3 Correct 20 ms 23748 KB Output is correct
4 Correct 20 ms 23676 KB Output is correct
5 Correct 20 ms 23748 KB Output is correct
6 Correct 20 ms 23736 KB Output is correct
7 Correct 20 ms 23756 KB Output is correct
8 Correct 21 ms 23752 KB Output is correct
9 Correct 20 ms 23748 KB Output is correct
10 Correct 21 ms 23760 KB Output is correct
11 Correct 20 ms 23744 KB Output is correct
12 Correct 20 ms 23752 KB Output is correct
13 Correct 20 ms 23756 KB Output is correct
14 Correct 20 ms 23748 KB Output is correct
15 Correct 20 ms 23752 KB Output is correct
16 Correct 23 ms 23708 KB Output is correct
17 Correct 21 ms 23760 KB Output is correct
18 Correct 19 ms 23764 KB Output is correct
19 Correct 26 ms 23736 KB Output is correct
20 Correct 334 ms 37208 KB Output is correct
21 Correct 316 ms 47212 KB Output is correct
22 Correct 236 ms 41768 KB Output is correct
23 Correct 479 ms 42316 KB Output is correct
24 Correct 204 ms 41728 KB Output is correct
25 Correct 261 ms 39460 KB Output is correct
26 Correct 269 ms 44904 KB Output is correct
27 Correct 294 ms 46228 KB Output is correct
28 Correct 336 ms 41628 KB Output is correct
29 Correct 197 ms 44452 KB Output is correct
30 Correct 342 ms 48168 KB Output is correct
31 Correct 1755 ms 47468 KB Output is correct
32 Incorrect 642 ms 46048 KB Output isn't correct
33 Halted 0 ms 0 KB -