oj.uz

Submission #615986

# Submission time Handle Problem Language Result Execution time Memory
615986 2022-07-31T17:21:48 Z amunduzbaev Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 882164 KB 
#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 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, 15, 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 100 ms 128600 KB Output is correct
2 Correct 122 ms 119988 KB Output is correct
3 Correct 99 ms 128616 KB Output is correct
4 Correct 102 ms 120028 KB Output is correct
5 Correct 109 ms 128592 KB Output is correct
6 Correct 98 ms 128588 KB Output is correct
7 Correct 100 ms 128632 KB Output is correct
8 Correct 105 ms 128568 KB Output is correct
9 Correct 105 ms 128616 KB Output is correct
10 Correct 106 ms 128672 KB Output is correct
11 Correct 101 ms 128624 KB Output is correct
12 Correct 102 ms 128660 KB Output is correct
13 Correct 101 ms 128588 KB Output is correct
14 Correct 102 ms 128600 KB Output is correct
15 Correct 110 ms 120012 KB Output is correct
16 Correct 113 ms 120220 KB Output is correct
17 Correct 115 ms 120136 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 128648 KB Output is correct
2 Correct 114 ms 120004 KB Output is correct
3 Correct 481 ms 165380 KB Output is correct
4 Correct 635 ms 174324 KB Output is correct
5 Correct 405 ms 168980 KB Output is correct
6 Correct 358 ms 165240 KB Output is correct
7 Incorrect 374 ms 169124 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 141672 KB Output is correct
2 Correct 3076 ms 453708 KB Output is correct
3 Correct 2987 ms 623400 KB Output is correct
4 Correct 3039 ms 857856 KB Output is correct
5 Correct 2922 ms 740620 KB Output is correct
6 Correct 3840 ms 737460 KB Output is correct
7 Correct 1193 ms 512012 KB Output is correct
8 Correct 2253 ms 882164 KB Output is correct
9 Execution timed out 4043 ms 604476 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 141672 KB Output is correct
2 Correct 3076 ms 453708 KB Output is correct
3 Correct 2987 ms 623400 KB Output is correct
4 Correct 3039 ms 857856 KB Output is correct
5 Correct 2922 ms 740620 KB Output is correct
6 Correct 3840 ms 737460 KB Output is correct
7 Correct 1193 ms 512012 KB Output is correct
8 Correct 2253 ms 882164 KB Output is correct
9 Execution timed out 4043 ms 604476 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 128600 KB Output is correct
2 Correct 122 ms 119988 KB Output is correct
3 Correct 99 ms 128616 KB Output is correct
4 Correct 102 ms 120028 KB Output is correct
5 Correct 109 ms 128592 KB Output is correct
6 Correct 98 ms 128588 KB Output is correct
7 Correct 100 ms 128632 KB Output is correct
8 Correct 105 ms 128568 KB Output is correct
9 Correct 105 ms 128616 KB Output is correct
10 Correct 106 ms 128672 KB Output is correct
11 Correct 101 ms 128624 KB Output is correct
12 Correct 102 ms 128660 KB Output is correct
13 Correct 101 ms 128588 KB Output is correct
14 Correct 102 ms 128600 KB Output is correct
15 Correct 110 ms 120012 KB Output is correct
16 Correct 113 ms 120220 KB Output is correct
17 Correct 115 ms 120136 KB Output is correct
18 Correct 109 ms 128648 KB Output is correct
19 Correct 114 ms 120004 KB Output is correct
20 Correct 481 ms 165380 KB Output is correct
21 Correct 635 ms 174324 KB Output is correct
22 Correct 405 ms 168980 KB Output is correct
23 Correct 358 ms 165240 KB Output is correct
24 Incorrect 374 ms 169124 KB Output isn't correct
25 Halted 0 ms 0 KB -