oj.uz

Submission #427658

# Submission time Handle Problem Language Result Execution time Memory
427658 2021-06-14T18:26:09 Z amoo_safar Sky Walking (IOI19_walk) C++17
43 / 100
 1661 ms 62544 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, 2ll * (x[s] - x[ Get_Last(0, s, _y[i]) ] )});
		}
		
		if(b != -1 && c != -1){
			G[b].pb({c, 2ll * (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);
	G[src].pb({src - 1, 0});

	mid.pb(des - 1);
	rgt.pb(des);
	G[des - 1].pb({des, 0});
	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 20 ms 23744 KB Output is correct
2 Correct 24 ms 23748 KB Output is correct
3 Correct 20 ms 23748 KB Output is correct
4 Correct 20 ms 23740 KB Output is correct
5 Correct 22 ms 23740 KB Output is correct
6 Correct 21 ms 23756 KB Output is correct
7 Correct 21 ms 23752 KB Output is correct
8 Correct 20 ms 23752 KB Output is correct
9 Correct 20 ms 23756 KB Output is correct
10 Correct 20 ms 23772 KB Output is correct
11 Correct 20 ms 23756 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 23744 KB Output is correct
15 Correct 20 ms 23712 KB Output is correct
16 Correct 20 ms 23740 KB Output is correct
17 Correct 20 ms 23752 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23744 KB Output is correct
2 Correct 20 ms 23756 KB Output is correct
3 Correct 289 ms 43356 KB Output is correct
4 Correct 284 ms 48168 KB Output is correct
5 Correct 228 ms 41752 KB Output is correct
6 Correct 490 ms 41832 KB Output is correct
7 Correct 206 ms 41732 KB Output is correct
8 Correct 282 ms 43584 KB Output is correct
9 Correct 269 ms 46704 KB Output is correct
10 Correct 311 ms 47760 KB Output is correct
11 Correct 320 ms 44076 KB Output is correct
12 Correct 199 ms 41932 KB Output is correct
13 Correct 315 ms 49692 KB Output is correct
14 Correct 1661 ms 45128 KB Output is correct
15 Incorrect 758 ms 44588 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 125 ms 33732 KB Output is correct
2 Correct 306 ms 43084 KB Output is correct
3 Correct 498 ms 43736 KB Output is correct
4 Correct 486 ms 49144 KB Output is correct
5 Correct 685 ms 51872 KB Output is correct
6 Correct 820 ms 55268 KB Output is correct
7 Correct 240 ms 38912 KB Output is correct
8 Correct 218 ms 42020 KB Output is correct
9 Correct 918 ms 62300 KB Output is correct
10 Correct 522 ms 54964 KB Output is correct
11 Correct 32 ms 25420 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 33732 KB Output is correct
2 Correct 306 ms 43084 KB Output is correct
3 Correct 498 ms 43736 KB Output is correct
4 Correct 486 ms 49144 KB Output is correct
5 Correct 685 ms 51872 KB Output is correct
6 Correct 820 ms 55268 KB Output is correct
7 Correct 240 ms 38912 KB Output is correct
8 Correct 218 ms 42020 KB Output is correct
9 Correct 918 ms 62300 KB Output is correct
10 Correct 522 ms 54964 KB Output is correct
11 Correct 32 ms 25420 KB Output is correct
12 Correct 378 ms 43776 KB Output is correct
13 Correct 450 ms 49204 KB Output is correct
14 Correct 665 ms 51876 KB Output is correct
15 Correct 353 ms 44616 KB Output is correct
16 Correct 443 ms 52088 KB Output is correct
17 Correct 406 ms 48552 KB Output is correct
18 Correct 378 ms 44580 KB Output is correct
19 Correct 422 ms 52000 KB Output is correct
20 Correct 268 ms 39620 KB Output is correct
21 Correct 53 ms 27592 KB Output is correct
22 Correct 287 ms 43996 KB Output is correct
23 Correct 261 ms 43868 KB Output is correct
24 Correct 221 ms 41084 KB Output is correct
25 Correct 262 ms 43100 KB Output is correct
26 Correct 214 ms 39804 KB Output is correct
27 Correct 677 ms 52144 KB Output is correct
28 Correct 344 ms 48804 KB Output is correct
29 Correct 722 ms 55392 KB Output is correct
30 Correct 212 ms 39056 KB Output is correct
31 Correct 828 ms 62544 KB Output is correct
32 Correct 393 ms 48944 KB Output is correct
33 Correct 278 ms 45968 KB Output is correct
34 Correct 514 ms 52920 KB Output is correct
35 Correct 305 ms 45956 KB Output is correct
36 Correct 239 ms 43384 KB Output is correct
37 Correct 237 ms 43028 KB Output is correct
38 Correct 212 ms 42052 KB Output is correct
39 Correct 594 ms 59132 KB Output is correct
40 Correct 247 ms 42752 KB Output is correct
41 Correct 247 ms 42964 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23744 KB Output is correct
2 Correct 24 ms 23748 KB Output is correct
3 Correct 20 ms 23748 KB Output is correct
4 Correct 20 ms 23740 KB Output is correct
5 Correct 22 ms 23740 KB Output is correct
6 Correct 21 ms 23756 KB Output is correct
7 Correct 21 ms 23752 KB Output is correct
8 Correct 20 ms 23752 KB Output is correct
9 Correct 20 ms 23756 KB Output is correct
10 Correct 20 ms 23772 KB Output is correct
11 Correct 20 ms 23756 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 23744 KB Output is correct
15 Correct 20 ms 23712 KB Output is correct
16 Correct 20 ms 23740 KB Output is correct
17 Correct 20 ms 23752 KB Output is correct
18 Correct 20 ms 23744 KB Output is correct
19 Correct 20 ms 23756 KB Output is correct
20 Correct 289 ms 43356 KB Output is correct
21 Correct 284 ms 48168 KB Output is correct
22 Correct 228 ms 41752 KB Output is correct
23 Correct 490 ms 41832 KB Output is correct
24 Correct 206 ms 41732 KB Output is correct
25 Correct 282 ms 43584 KB Output is correct
26 Correct 269 ms 46704 KB Output is correct
27 Correct 311 ms 47760 KB Output is correct
28 Correct 320 ms 44076 KB Output is correct
29 Correct 199 ms 41932 KB Output is correct
30 Correct 315 ms 49692 KB Output is correct
31 Correct 1661 ms 45128 KB Output is correct
32 Incorrect 758 ms 44588 KB Output isn't correct
33 Halted 0 ms 0 KB -