Submission #615991

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
615991	2022-07-31T17:25:08 Z	amunduzbaev	Sky Walking (IOI19_walk)	C++17	57 / 100	3983 ms	883624 KB

walk

#include "bits/stdc++.h"
using namespace std;
#include "walk.h"

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
const ll inf = 2e18;
const int N = 1e5 + 5;

struct ST{
	vector<ll> tree;
	vector<ar<int, 2>> c;
	int last;
	void add(){
		tree.push_back(inf);
		c.push_back({});
		last++;
	}
	
	ST(){ add(); }
	
	void umin(int i, ll v, int lx = 0, int rx = N, int x = 0){
		if(lx == rx) {
			tree[x] = min(tree[x], v);
			return;
		} int m = (lx + rx) >> 1;
		if(i <= m){
			if(!c[x][0]) c[x][0] = last, add();
			umin(i, v, lx, m, c[x][0]);
		} else {
			if(!c[x][1]) c[x][1] = last, add();
			umin(i, v, m + 1, rx, c[x][1]);
		}
		
		tree[x] = inf;
		if(c[x][0]) tree[x] = min(tree[x], tree[c[x][0]]);
		if(c[x][1]) tree[x] = min(tree[x], tree[c[x][1]]);
	}
	
	ll get(int l, int r, int lx = 0, int rx = N, int x = 0){
		if(lx > r || rx < l) return inf;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		ll res = inf;
		if(c[x][0]) res = min(res, get(l, r, lx, m, c[x][0]));
		if(c[x][1]) res = min(res, get(l, r, m + 1, rx, c[x][1]));
		
		return res;
	}
};

struct ST2{
	ST tree[N << 2];
	
	void umin(int i, int j, ll v, int lx = 0, int rx = N, int x = 1){
		tree[x].umin(j, v);
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		if(i <= m) umin(i, j, v, lx, m, x << 1);
		else umin(i, j, v, m + 1, rx, x << 1 | 1);
	}
	
	ll get(int l, int r, int l_, int r_, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return inf;
		if(lx >= l && rx <= r){
			return tree[x].get(l_, r_);
		}
		
		int m = (lx + rx) >> 1;
		return min(get(l, r, l_, r_, lx, m, x << 1), get(l, r, l_, r_, m + 1, rx, x << 1 | 1));
	}
}add, sub;

vector<ar<int, 2>> edges[N * 11];
ll d[N * 11];

#define sow cout<<"here"<<endl;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n = x.size();
	if(s == 0 && g == n - 1){
		int n = x.size(), q = l.size();
		vector<int> p(q); iota(p.begin(), p.end(), 0);
		sort(p.begin(), p.end(), [&](int i, int j){
			return r[i] < r[j];
		});
		
		vector<int> tot;
		vector<ll> dp(q, inf);
		for(int i=0;i<q;i++){
			tot.push_back(y[i]);
		}
		
		sort(tot.begin(), tot.end());
		tot.erase(unique(tot.begin(), tot.end()), tot.end());
		ll res = inf;
		sub.umin(0, 0, 0);
		add.umin(0, 0, 0);
		for(auto i : p){
			int j = lower_bound(tot.begin(), tot.end(), y[i]) - tot.begin() + 1;
			dp[i] = min(dp[i], sub.get(l[i], r[i], 0, j) + y[i]);
			dp[i] = min(dp[i], add.get(l[i], r[i], j, q) - y[i]);
			sub.umin(r[i], j, dp[i] - y[i]);
			add.umin(r[i], j, dp[i] + y[i]);
			if(r[i] == n - 1) res = min(res, dp[i] + y[i]);
		}
		
		res += (x[n - 1] - x[0]);
		if(res < 1e18){
			return res;
		} else {
			return -1;
		}
	} else {
		int q = l.size();
		
		vector<int> p(q); iota(p.begin(), p.end(), 0);
		sort(p.begin(), p.end(), [&](int i, int j){
			return y[i] > y[j];
		});
		
		vector<int> P(n); iota(P.begin(), P.end(), 0);
		sort(P.begin(), P.end(), [&](int i, int j){
			return h[i] > h[j];
		});
		
		vector<int> last(n, -1), id(n, -1);
		set<int> ss;
		int j = 0, v = 0;
		for(auto i : p){
			while(j < n && h[P[j]] >= y[i]){
				ss.insert(P[j]);
				j++;
			}
			//~ for(auto x : ss) cout<<x<<" ";
			//~ cout<<"\n";
			//~ cout<<l[i]<<" "<<r[i]<<"\n";
			//~ int k = lower_bound(x.begin(), x.end(), l[i]) - x.begin();
			auto it = ss.lower_bound(l[i]);
			int tmp = -1, X = -1;
			while(it != ss.end() && *it <= r[i]){
				int k = *it;
				//~ cout<<k<<" ";
				if(~tmp){
					edges[v].push_back({tmp, x[k] - X});
					edges[tmp].push_back({v, x[k] - X});
				}
				if(~last[k]){
					edges[v].push_back({last[k], y[id[k]] - y[i]});
					edges[last[k]].push_back({v, y[id[k]] - y[i]});
				}
				last[k] = v, id[k] = i;
				tmp = v, X = x[*it];
				v++;
				it++;
			}
			
			//~ cout<<"\n";
		}
		
		for(int i=0;i<n;i++){
			if(~last[i]){
				edges[v].push_back({last[i], y[id[i]]});
				edges[last[i]].push_back({v, y[id[i]]});
				last[i] = v;
				v++;
			}
		}
		
		//~ last[s], last[g]
		if(last[s] == -1 || last[g] == -1) return -1;
		s = last[s], g = last[g];
		memset(d, 31, sizeof d);
		priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>> > pq;
		d[s] = 0; pq.push({0, s});
		while(!pq.empty()){
			auto [D, u] = pq.top(); pq.pop();
			if(D > d[u]) continue;
			for(auto x : edges[u]){
				if(d[x[0]] > d[u] + x[1]){
					d[x[0]] = d[u] + x[1];
					pq.push({d[x[0]], x[0]});
				}
			}
		}
		
		if(d[g] > inf) return -1;
		return d[g];
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	128616 KB	Output is correct
2	Correct	111 ms	120016 KB	Output is correct
3	Correct	98 ms	128588 KB	Output is correct
4	Correct	93 ms	120036 KB	Output is correct
5	Correct	99 ms	128688 KB	Output is correct
6	Correct	109 ms	128692 KB	Output is correct
7	Correct	101 ms	128656 KB	Output is correct
8	Correct	100 ms	128564 KB	Output is correct
9	Correct	99 ms	128592 KB	Output is correct
10	Correct	124 ms	128716 KB	Output is correct
11	Correct	101 ms	128620 KB	Output is correct
12	Correct	103 ms	128616 KB	Output is correct
13	Correct	112 ms	128632 KB	Output is correct
14	Correct	103 ms	128572 KB	Output is correct
15	Correct	104 ms	120012 KB	Output is correct
16	Correct	121 ms	120132 KB	Output is correct
17	Correct	116 ms	120168 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	102 ms	128548 KB	Output is correct
2	Correct	124 ms	119956 KB	Output is correct
3	Correct	463 ms	165500 KB	Output is correct
4	Correct	622 ms	174268 KB	Output is correct
5	Correct	385 ms	168920 KB	Output is correct
6	Correct	360 ms	165160 KB	Output is correct
7	Correct	383 ms	168968 KB	Output is correct
8	Correct	590 ms	174744 KB	Output is correct
9	Correct	440 ms	167488 KB	Output is correct
10	Correct	735 ms	188632 KB	Output is correct
11	Correct	381 ms	151640 KB	Output is correct
12	Correct	2169 ms	880236 KB	Output is correct
13	Correct	2129 ms	883624 KB	Output is correct
14	Correct	263 ms	140432 KB	Output is correct
15	Correct	290 ms	149812 KB	Output is correct
16	Correct	280 ms	149704 KB	Output is correct
17	Correct	297 ms	148940 KB	Output is correct
18	Correct	3214 ms	237260 KB	Output is correct
19	Correct	105 ms	129612 KB	Output is correct
20	Correct	170 ms	138756 KB	Output is correct
21	Correct	1032 ms	271864 KB	Output is correct
22	Correct	1093 ms	321120 KB	Output is correct
23	Correct	2503 ms	385664 KB	Output is correct
24	Correct	1140 ms	332304 KB	Output is correct
25	Correct	1056 ms	296904 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	493 ms	141648 KB	Output is correct
2	Correct	3266 ms	453572 KB	Output is correct
3	Correct	3399 ms	623236 KB	Output is correct
4	Correct	3215 ms	857776 KB	Output is correct
5	Correct	3197 ms	740528 KB	Output is correct
6	Correct	3983 ms	737100 KB	Output is correct
7	Correct	1296 ms	511888 KB	Output is correct
8	Correct	2238 ms	881876 KB	Output is correct
9	Correct	3889 ms	604520 KB	Output is correct
10	Correct	1676 ms	285756 KB	Output is correct
11	Correct	129 ms	121956 KB	Output is correct

Subtask #4

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	493 ms	141648 KB	Output is correct
2	Correct	3266 ms	453572 KB	Output is correct
3	Correct	3399 ms	623236 KB	Output is correct
4	Correct	3215 ms	857776 KB	Output is correct
5	Correct	3197 ms	740528 KB	Output is correct
6	Correct	3983 ms	737100 KB	Output is correct
7	Correct	1296 ms	511888 KB	Output is correct
8	Correct	2238 ms	881876 KB	Output is correct
9	Correct	3889 ms	604520 KB	Output is correct
10	Correct	1676 ms	285756 KB	Output is correct
11	Correct	129 ms	121956 KB	Output is correct
12	Correct	2878 ms	619036 KB	Output is correct
13	Correct	2961 ms	851952 KB	Output is correct
14	Correct	2884 ms	736544 KB	Output is correct
15	Correct	1798 ms	555512 KB	Output is correct
16	Correct	1741 ms	473040 KB	Output is correct
17	Correct	1814 ms	497412 KB	Output is correct
18	Correct	1904 ms	555428 KB	Output is correct
19	Correct	1716 ms	472784 KB	Output is correct
20	Correct	1478 ms	490648 KB	Output is correct
21	Correct	156 ms	126356 KB	Output is correct
22	Correct	1620 ms	564280 KB	Output is correct
23	Correct	1599 ms	609628 KB	Output is correct
24	Correct	1615 ms	616008 KB	Output is correct
25	Correct	1752 ms	671392 KB	Output is correct
26	Correct	1595 ms	573828 KB	Output is correct
27	Correct	3351 ms	747796 KB	Output is correct
28	Correct	2536 ms	857044 KB	Output is correct
29	Correct	3763 ms	730196 KB	Output is correct
30	Correct	1194 ms	510088 KB	Output is correct
31	Correct	3745 ms	603160 KB	Output is correct
32	Correct	1344 ms	317128 KB	Output is correct
33	Correct	1379 ms	329056 KB	Output is correct
34	Correct	1873 ms	365852 KB	Output is correct
35	Correct	1477 ms	423308 KB	Output is correct
36	Correct	1389 ms	455664 KB	Output is correct
37	Correct	1027 ms	271992 KB	Output is correct
38	Correct	1110 ms	321128 KB	Output is correct
39	Correct	2509 ms	385584 KB	Output is correct
40	Correct	1125 ms	332228 KB	Output is correct
41	Correct	1106 ms	296824 KB	Output is correct

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	128616 KB	Output is correct
2	Correct	111 ms	120016 KB	Output is correct
3	Correct	98 ms	128588 KB	Output is correct
4	Correct	93 ms	120036 KB	Output is correct
5	Correct	99 ms	128688 KB	Output is correct
6	Correct	109 ms	128692 KB	Output is correct
7	Correct	101 ms	128656 KB	Output is correct
8	Correct	100 ms	128564 KB	Output is correct
9	Correct	99 ms	128592 KB	Output is correct
10	Correct	124 ms	128716 KB	Output is correct
11	Correct	101 ms	128620 KB	Output is correct
12	Correct	103 ms	128616 KB	Output is correct
13	Correct	112 ms	128632 KB	Output is correct
14	Correct	103 ms	128572 KB	Output is correct
15	Correct	104 ms	120012 KB	Output is correct
16	Correct	121 ms	120132 KB	Output is correct
17	Correct	116 ms	120168 KB	Output is correct
18	Correct	102 ms	128548 KB	Output is correct
19	Correct	124 ms	119956 KB	Output is correct
20	Correct	463 ms	165500 KB	Output is correct
21	Correct	622 ms	174268 KB	Output is correct
22	Correct	385 ms	168920 KB	Output is correct
23	Correct	360 ms	165160 KB	Output is correct
24	Correct	383 ms	168968 KB	Output is correct
25	Correct	590 ms	174744 KB	Output is correct
26	Correct	440 ms	167488 KB	Output is correct
27	Correct	735 ms	188632 KB	Output is correct
28	Correct	381 ms	151640 KB	Output is correct
29	Correct	2169 ms	880236 KB	Output is correct
30	Correct	2129 ms	883624 KB	Output is correct
31	Correct	263 ms	140432 KB	Output is correct
32	Correct	290 ms	149812 KB	Output is correct
33	Correct	280 ms	149704 KB	Output is correct
34	Correct	297 ms	148940 KB	Output is correct
35	Correct	3214 ms	237260 KB	Output is correct
36	Correct	105 ms	129612 KB	Output is correct
37	Correct	170 ms	138756 KB	Output is correct
38	Correct	1032 ms	271864 KB	Output is correct
39	Correct	1093 ms	321120 KB	Output is correct
40	Correct	2503 ms	385664 KB	Output is correct
41	Correct	1140 ms	332304 KB	Output is correct
42	Correct	1056 ms	296904 KB	Output is correct
43	Correct	493 ms	141648 KB	Output is correct
44	Correct	3266 ms	453572 KB	Output is correct
45	Correct	3399 ms	623236 KB	Output is correct
46	Correct	3215 ms	857776 KB	Output is correct
47	Correct	3197 ms	740528 KB	Output is correct
48	Correct	3983 ms	737100 KB	Output is correct
49	Correct	1296 ms	511888 KB	Output is correct
50	Correct	2238 ms	881876 KB	Output is correct
51	Correct	3889 ms	604520 KB	Output is correct
52	Correct	1676 ms	285756 KB	Output is correct
53	Correct	129 ms	121956 KB	Output is correct
54	Correct	2878 ms	619036 KB	Output is correct
55	Correct	2961 ms	851952 KB	Output is correct
56	Correct	2884 ms	736544 KB	Output is correct
57	Correct	1798 ms	555512 KB	Output is correct
58	Correct	1741 ms	473040 KB	Output is correct
59	Correct	1814 ms	497412 KB	Output is correct
60	Correct	1904 ms	555428 KB	Output is correct
61	Correct	1716 ms	472784 KB	Output is correct
62	Correct	1478 ms	490648 KB	Output is correct
63	Correct	156 ms	126356 KB	Output is correct
64	Correct	1620 ms	564280 KB	Output is correct
65	Correct	1599 ms	609628 KB	Output is correct
66	Correct	1615 ms	616008 KB	Output is correct
67	Correct	1752 ms	671392 KB	Output is correct
68	Correct	1595 ms	573828 KB	Output is correct
69	Correct	3351 ms	747796 KB	Output is correct
70	Correct	2536 ms	857044 KB	Output is correct
71	Correct	3763 ms	730196 KB	Output is correct
72	Correct	1194 ms	510088 KB	Output is correct
73	Correct	3745 ms	603160 KB	Output is correct
74	Correct	1344 ms	317128 KB	Output is correct
75	Correct	1379 ms	329056 KB	Output is correct
76	Correct	1873 ms	365852 KB	Output is correct
77	Correct	1477 ms	423308 KB	Output is correct
78	Correct	1389 ms	455664 KB	Output is correct
79	Correct	1027 ms	271992 KB	Output is correct
80	Correct	1110 ms	321128 KB	Output is correct
81	Correct	2509 ms	385584 KB	Output is correct
82	Correct	1125 ms	332228 KB	Output is correct
83	Correct	1106 ms	296824 KB	Output is correct
84	Correct	151 ms	135564 KB	Output is correct
85	Runtime error	448 ms	356712 KB	Execution killed with signal 11
86	Halted	0 ms	0 KB	-