oj.uz

Submission #427651

# Submission time Handle Problem Language Result Execution time Memory
427651 2021-06-14T18:23:18 Z amoo_safar Sky Walking (IOI19_walk) C++17
43 / 100
 1852 ms 62396 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< pair<ll, ll> > 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);
	ll max_len = 2000000000ll;
	return ans > 1ll * (n + m) * max_len ? -1 : ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23748 KB Output is correct
2 Correct 23 ms 23756 KB Output is correct
3 Correct 24 ms 23748 KB Output is correct
4 Correct 24 ms 23744 KB Output is correct
5 Correct 25 ms 23744 KB Output is correct
6 Correct 23 ms 23708 KB Output is correct
7 Correct 24 ms 23784 KB Output is correct
8 Correct 23 ms 23756 KB Output is correct
9 Correct 22 ms 23748 KB Output is correct
10 Correct 26 ms 23752 KB Output is correct
11 Correct 25 ms 23752 KB Output is correct
12 Correct 23 ms 23756 KB Output is correct
13 Correct 26 ms 23748 KB Output is correct
14 Correct 26 ms 23792 KB Output is correct
15 Correct 25 ms 23724 KB Output is correct
16 Correct 25 ms 23756 KB Output is correct
17 Correct 24 ms 23748 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23744 KB Output is correct
2 Correct 24 ms 23744 KB Output is correct
3 Correct 324 ms 43504 KB Output is correct
4 Correct 281 ms 48312 KB Output is correct
5 Correct 221 ms 41700 KB Output is correct
6 Correct 510 ms 41724 KB Output is correct
7 Correct 218 ms 41732 KB Output is correct
8 Correct 294 ms 43552 KB Output is correct
9 Correct 314 ms 46708 KB Output is correct
10 Correct 327 ms 47920 KB Output is correct
11 Correct 269 ms 44084 KB Output is correct
12 Correct 207 ms 42040 KB Output is correct
13 Correct 350 ms 49644 KB Output is correct
14 Correct 1852 ms 44892 KB Output is correct
15 Incorrect 698 ms 44456 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 133 ms 33640 KB Output is correct
2 Correct 337 ms 43164 KB Output is correct
3 Correct 409 ms 43836 KB Output is correct
4 Correct 539 ms 49288 KB Output is correct
5 Correct 635 ms 51876 KB Output is correct
6 Correct 849 ms 55356 KB Output is correct
7 Correct 229 ms 38904 KB Output is correct
8 Correct 259 ms 41932 KB Output is correct
9 Correct 833 ms 62396 KB Output is correct
10 Correct 461 ms 55064 KB Output is correct
11 Correct 35 ms 25412 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 33640 KB Output is correct
2 Correct 337 ms 43164 KB Output is correct
3 Correct 409 ms 43836 KB Output is correct
4 Correct 539 ms 49288 KB Output is correct
5 Correct 635 ms 51876 KB Output is correct
6 Correct 849 ms 55356 KB Output is correct
7 Correct 229 ms 38904 KB Output is correct
8 Correct 259 ms 41932 KB Output is correct
9 Correct 833 ms 62396 KB Output is correct
10 Correct 461 ms 55064 KB Output is correct
11 Correct 35 ms 25412 KB Output is correct
12 Correct 394 ms 43860 KB Output is correct
13 Correct 466 ms 49140 KB Output is correct
14 Correct 666 ms 51908 KB Output is correct
15 Correct 448 ms 44584 KB Output is correct
16 Correct 456 ms 52036 KB Output is correct
17 Correct 422 ms 48548 KB Output is correct
18 Correct 374 ms 44596 KB Output is correct
19 Correct 446 ms 52064 KB Output is correct
20 Correct 262 ms 39424 KB Output is correct
21 Correct 54 ms 27460 KB Output is correct
22 Correct 308 ms 44144 KB Output is correct
23 Correct 252 ms 43808 KB Output is correct
24 Correct 288 ms 41040 KB Output is correct
25 Correct 243 ms 43256 KB Output is correct
26 Correct 220 ms 39756 KB Output is correct
27 Correct 649 ms 52268 KB Output is correct
28 Correct 350 ms 48828 KB Output is correct
29 Correct 711 ms 55348 KB Output is correct
30 Correct 221 ms 39040 KB Output is correct
31 Correct 887 ms 62340 KB Output is correct
32 Correct 318 ms 48928 KB Output is correct
33 Correct 272 ms 45840 KB Output is correct
34 Correct 447 ms 52992 KB Output is correct
35 Correct 319 ms 45880 KB Output is correct
36 Correct 242 ms 43476 KB Output is correct
37 Correct 218 ms 42916 KB Output is correct
38 Correct 222 ms 42036 KB Output is correct
39 Correct 554 ms 59040 KB Output is correct
40 Correct 236 ms 42660 KB Output is correct
41 Correct 257 ms 42832 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23748 KB Output is correct
2 Correct 23 ms 23756 KB Output is correct
3 Correct 24 ms 23748 KB Output is correct
4 Correct 24 ms 23744 KB Output is correct
5 Correct 25 ms 23744 KB Output is correct
6 Correct 23 ms 23708 KB Output is correct
7 Correct 24 ms 23784 KB Output is correct
8 Correct 23 ms 23756 KB Output is correct
9 Correct 22 ms 23748 KB Output is correct
10 Correct 26 ms 23752 KB Output is correct
11 Correct 25 ms 23752 KB Output is correct
12 Correct 23 ms 23756 KB Output is correct
13 Correct 26 ms 23748 KB Output is correct
14 Correct 26 ms 23792 KB Output is correct
15 Correct 25 ms 23724 KB Output is correct
16 Correct 25 ms 23756 KB Output is correct
17 Correct 24 ms 23748 KB Output is correct
18 Correct 21 ms 23744 KB Output is correct
19 Correct 24 ms 23744 KB Output is correct
20 Correct 324 ms 43504 KB Output is correct
21 Correct 281 ms 48312 KB Output is correct
22 Correct 221 ms 41700 KB Output is correct
23 Correct 510 ms 41724 KB Output is correct
24 Correct 218 ms 41732 KB Output is correct
25 Correct 294 ms 43552 KB Output is correct
26 Correct 314 ms 46708 KB Output is correct
27 Correct 327 ms 47920 KB Output is correct
28 Correct 269 ms 44084 KB Output is correct
29 Correct 207 ms 42040 KB Output is correct
30 Correct 350 ms 49644 KB Output is correct
31 Correct 1852 ms 44892 KB Output is correct
32 Incorrect 698 ms 44456 KB Output isn't correct
33 Halted 0 ms 0 KB -