oj.uz

Submission #427576

# Submission time Handle Problem Language Result Execution time Memory
427576 2021-06-14T17:23:09 Z amoo_safar Sky Walking (IOI19_walk) C++17
33 / 100
 717 ms 32080 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 = 1e5 + 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]){
			if(dis[adj] > dis[fr] + w){
				st.erase({dis[adj], adj});
				dis[adj] = dis[fr] + w;
				st.insert({dis[adj], adj});
			}
		}
	}
	return dis[des];
}

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;

	ll ans = x[g] - x[s];
	
	_l.pb(s); _r.pb(s); _y.pb(0);
	_l.pb(g); _r.pb(g); _y.pb(0);
	
	int src = _l.size() - 2;
	int des = _r.size() - 1;

	n = _x.size();
	m = _l.size();
	
	l = _l;
	r = _r;
	y = _y;

	vector<int> lft, mid, rgt;
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 15340 KB Output is correct
2 Correct 323 ms 21540 KB Output is correct
3 Correct 391 ms 22188 KB Output is correct
4 Correct 501 ms 27568 KB Output is correct
5 Correct 664 ms 28860 KB Output is correct
6 Correct 569 ms 29020 KB Output is correct
7 Correct 222 ms 20416 KB Output is correct
8 Correct 208 ms 25192 KB Output is correct
9 Correct 614 ms 30532 KB Output is correct
10 Correct 345 ms 29228 KB Output is correct
11 Correct 21 ms 9804 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 15340 KB Output is correct
2 Correct 323 ms 21540 KB Output is correct
3 Correct 391 ms 22188 KB Output is correct
4 Correct 501 ms 27568 KB Output is correct
5 Correct 664 ms 28860 KB Output is correct
6 Correct 569 ms 29020 KB Output is correct
7 Correct 222 ms 20416 KB Output is correct
8 Correct 208 ms 25192 KB Output is correct
9 Correct 614 ms 30532 KB Output is correct
10 Correct 345 ms 29228 KB Output is correct
11 Correct 21 ms 9804 KB Output is correct
12 Correct 367 ms 22172 KB Output is correct
13 Correct 438 ms 27692 KB Output is correct
14 Correct 717 ms 28968 KB Output is correct
15 Correct 368 ms 26284 KB Output is correct
16 Correct 430 ms 30224 KB Output is correct
17 Correct 456 ms 28072 KB Output is correct
18 Correct 361 ms 26280 KB Output is correct
19 Correct 481 ms 30224 KB Output is correct
20 Correct 295 ms 20352 KB Output is correct
21 Correct 39 ms 11596 KB Output is correct
22 Correct 267 ms 23876 KB Output is correct
23 Correct 306 ms 23988 KB Output is correct
24 Correct 230 ms 22668 KB Output is correct
25 Correct 236 ms 23624 KB Output is correct
26 Correct 236 ms 22944 KB Output is correct
27 Correct 641 ms 29420 KB Output is correct
28 Correct 367 ms 27316 KB Output is correct
29 Correct 603 ms 29060 KB Output is correct
30 Correct 204 ms 20376 KB Output is correct
31 Correct 605 ms 30592 KB Output is correct
32 Correct 259 ms 26636 KB Output is correct
33 Correct 251 ms 26800 KB Output is correct
34 Correct 301 ms 31528 KB Output is correct
35 Correct 305 ms 29224 KB Output is correct
36 Correct 241 ms 28016 KB Output is correct
37 Correct 222 ms 27364 KB Output is correct
38 Correct 257 ms 28252 KB Output is correct
39 Correct 328 ms 32080 KB Output is correct
40 Correct 249 ms 28032 KB Output is correct
41 Correct 273 ms 27364 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8012 KB Output isn't correct
2 Halted 0 ms 0 KB -