oj.uz

Submission #542677

# Submission time Handle Problem Language Result Execution time Memory
542677 2022-03-27T13:27:13 Z jamezzz Sky Walking (IOI19_walk) C++17
100 / 100
 1382 ms 145680 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll,int> li;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

struct skywalk{
	int l,r,h;
};

#define maxn 100005

int n,m;
vector<ii> nodes,nodes2;
vector<skywalk> skywalks;
vector<int> add[maxn],rem[maxn];
ll dist[3000005];
priority_queue<li,vector<li>,greater<li>> pq;
vii AL[3000005];

void proc(int a,vi &h){
	vector<skywalk> tmp;
	vector<ii> pv,nx;
	pv.pb({h[a],a});
	nx.pb({h[a],a});
	for(int i=a-1;i>=0;--i){
		if(h[i]>pv.back().fi){
			pv.pb({h[i],i});
		}
	}
	for(int i=a+1;i<n;++i){
		if(h[i]>nx.back().fi){
			nx.pb({h[i],i});
		}
	}
	for(skywalk &sw:skywalks){
		if(sw.l<a&&a<sw.r){
			int p1=lower_bound(all(pv),ii(sw.h,-1))-pv.begin();
			int p2=lower_bound(all(nx),ii(sw.h,-1))-nx.begin();
			if(sw.l!=pv[p1].se)tmp.pb({sw.l,pv[p1].se,sw.h});
			if(pv[p1].se!=nx[p2].se)tmp.pb({pv[p1].se,nx[p2].se,sw.h});
			if(nx[p2].se!=sw.r)tmp.pb({nx[p2].se,sw.r,sw.h});
		}
		else tmp.pb(sw);
	}
	swap(tmp,skywalks);
}

ll min_distance(vi x,vi h,vi l,vi r,vi y,int s,int g){
	n=sz(x);m=sz(l);
	for(int i=0;i<m;++i){
		skywalks.pb({l[i],r[i],y[i]});
	}
	proc(s,h);proc(g,h);
	
	for(skywalk &sw:skywalks){
		add[sw.l].pb(sw.h);
		rem[sw.r].pb(sw.h);
	}
	
	multiset<int> ms;
	ms.insert(0);
	for(int i=0;i<n;++i){
		for(int j:add[i])ms.insert(j);
		for(int j:add[i]){
			nodes.pb({x[i],j});
			nodes.pb({x[i],*(--ms.lower_bound(j))});
		}
		for(int j:rem[i]){
			nodes.pb({x[i],j});
			nodes.pb({x[i],*(--ms.lower_bound(j))});
		}
		for(int j:rem[i])ms.erase(ms.find(j));
	}
	disc(nodes);
	
	for(ii pr:nodes)nodes2.pb({pr.se,pr.fi});
	sort(all(nodes2));
	
	for(int i=1;i<sz(nodes);++i){
		if(nodes[i-1].fi==nodes[i].fi){
			AL[i-1].pb({i,nodes[i].se-nodes[i-1].se});
			AL[i].pb({i-1,nodes[i].se-nodes[i-1].se});
		}
	}
	
	for(skywalk &sw:skywalks){
		int s=lower_bound(all(nodes2),ii(sw.h,x[sw.l]))-nodes2.begin();
		while(nodes2[s]!=ii(sw.h,x[sw.r])){
			ii p1={nodes2[s].se,nodes2[s].fi};
			ii p2={nodes2[s+1].se,nodes2[s+1].fi};
			int u=lower_bound(all(nodes),p1)-nodes.begin();
			int v=lower_bound(all(nodes),p2)-nodes.begin();
			int w=p2.fi-p1.fi;
			AL[u].pb({v,w});
			AL[v].pb({u,w});
			++s;
		}
	}
	
	for(int i=0;i<sz(nodes);++i)dist[i]=LINF;
	int src=lower_bound(all(nodes),ii(x[s],0))-nodes.begin();
	if(src==sz(nodes)||nodes[src]!=ii(x[s],0))return -1;
	dist[src]=0;pq.push({0,src});
	
	while(!pq.empty()){
		auto[d,u]=pq.top();
		pq.pop();
		for(auto[v,w]:AL[u]){
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				pq.push({dist[v],v});
			}
		}
	}
	
	int f=lower_bound(all(nodes),ii(x[g],0))-nodes.begin();
	if(f==sz(nodes)||nodes[f]!=ii(x[g],0))return -1;
	ll ans=dist[f];
	if(ans==LINF)ans=-1;
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 75352 KB Output is correct
2 Correct 36 ms 75444 KB Output is correct
3 Correct 35 ms 75472 KB Output is correct
4 Correct 36 ms 75340 KB Output is correct
5 Correct 35 ms 75428 KB Output is correct
6 Correct 36 ms 75468 KB Output is correct
7 Correct 38 ms 75408 KB Output is correct
8 Correct 37 ms 75392 KB Output is correct
9 Correct 36 ms 75400 KB Output is correct
10 Correct 34 ms 75428 KB Output is correct
11 Correct 36 ms 75476 KB Output is correct
12 Correct 37 ms 75372 KB Output is correct
13 Correct 34 ms 75444 KB Output is correct
14 Correct 35 ms 75352 KB Output is correct
15 Correct 34 ms 75452 KB Output is correct
16 Correct 34 ms 75420 KB Output is correct
17 Correct 36 ms 75460 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 75448 KB Output is correct
2 Correct 36 ms 75348 KB Output is correct
3 Correct 509 ms 107384 KB Output is correct
4 Correct 500 ms 111912 KB Output is correct
5 Correct 317 ms 102736 KB Output is correct
6 Correct 330 ms 102156 KB Output is correct
7 Correct 340 ms 102980 KB Output is correct
8 Correct 525 ms 108736 KB Output is correct
9 Correct 418 ms 109184 KB Output is correct
10 Correct 544 ms 111060 KB Output is correct
11 Correct 456 ms 107980 KB Output is correct
12 Correct 362 ms 112648 KB Output is correct
13 Correct 575 ms 118016 KB Output is correct
14 Correct 404 ms 106788 KB Output is correct
15 Correct 426 ms 110412 KB Output is correct
16 Correct 419 ms 109100 KB Output is correct
17 Correct 409 ms 107920 KB Output is correct
18 Correct 502 ms 105692 KB Output is correct
19 Correct 54 ms 76968 KB Output is correct
20 Correct 147 ms 91804 KB Output is correct
21 Correct 404 ms 107208 KB Output is correct
22 Correct 381 ms 111924 KB Output is correct
23 Correct 488 ms 112132 KB Output is correct
24 Correct 389 ms 110372 KB Output is correct
25 Correct 391 ms 107812 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 84232 KB Output is correct
2 Correct 738 ms 113120 KB Output is correct
3 Correct 735 ms 114348 KB Output is correct
4 Correct 841 ms 119428 KB Output is correct
5 Correct 924 ms 120888 KB Output is correct
6 Correct 750 ms 118572 KB Output is correct
7 Correct 329 ms 100164 KB Output is correct
8 Correct 324 ms 112976 KB Output is correct
9 Correct 697 ms 118796 KB Output is correct
10 Correct 355 ms 108044 KB Output is correct
11 Correct 47 ms 77012 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 84232 KB Output is correct
2 Correct 738 ms 113120 KB Output is correct
3 Correct 735 ms 114348 KB Output is correct
4 Correct 841 ms 119428 KB Output is correct
5 Correct 924 ms 120888 KB Output is correct
6 Correct 750 ms 118572 KB Output is correct
7 Correct 329 ms 100164 KB Output is correct
8 Correct 324 ms 112976 KB Output is correct
9 Correct 697 ms 118796 KB Output is correct
10 Correct 355 ms 108044 KB Output is correct
11 Correct 47 ms 77012 KB Output is correct
12 Correct 665 ms 114424 KB Output is correct
13 Correct 568 ms 118432 KB Output is correct
14 Correct 751 ms 120908 KB Output is correct
15 Correct 572 ms 117716 KB Output is correct
16 Correct 512 ms 113960 KB Output is correct
17 Correct 592 ms 118248 KB Output is correct
18 Correct 562 ms 117804 KB Output is correct
19 Correct 528 ms 113924 KB Output is correct
20 Correct 322 ms 99184 KB Output is correct
21 Correct 61 ms 79352 KB Output is correct
22 Correct 459 ms 110360 KB Output is correct
23 Correct 422 ms 110076 KB Output is correct
24 Correct 331 ms 106960 KB Output is correct
25 Correct 382 ms 108404 KB Output is correct
26 Correct 298 ms 106876 KB Output is correct
27 Correct 730 ms 121080 KB Output is correct
28 Correct 527 ms 118424 KB Output is correct
29 Correct 678 ms 118420 KB Output is correct
30 Correct 310 ms 100172 KB Output is correct
31 Correct 650 ms 118648 KB Output is correct
32 Correct 316 ms 107664 KB Output is correct
33 Correct 317 ms 110140 KB Output is correct
34 Correct 396 ms 109608 KB Output is correct
35 Correct 397 ms 111196 KB Output is correct
36 Correct 333 ms 108888 KB Output is correct
37 Correct 309 ms 107152 KB Output is correct
38 Correct 297 ms 111980 KB Output is correct
39 Correct 411 ms 112148 KB Output is correct
40 Correct 313 ms 110280 KB Output is correct
41 Correct 310 ms 107788 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 75352 KB Output is correct
2 Correct 36 ms 75444 KB Output is correct
3 Correct 35 ms 75472 KB Output is correct
4 Correct 36 ms 75340 KB Output is correct
5 Correct 35 ms 75428 KB Output is correct
6 Correct 36 ms 75468 KB Output is correct
7 Correct 38 ms 75408 KB Output is correct
8 Correct 37 ms 75392 KB Output is correct
9 Correct 36 ms 75400 KB Output is correct
10 Correct 34 ms 75428 KB Output is correct
11 Correct 36 ms 75476 KB Output is correct
12 Correct 37 ms 75372 KB Output is correct
13 Correct 34 ms 75444 KB Output is correct
14 Correct 35 ms 75352 KB Output is correct
15 Correct 34 ms 75452 KB Output is correct
16 Correct 34 ms 75420 KB Output is correct
17 Correct 36 ms 75460 KB Output is correct
18 Correct 37 ms 75448 KB Output is correct
19 Correct 36 ms 75348 KB Output is correct
20 Correct 509 ms 107384 KB Output is correct
21 Correct 500 ms 111912 KB Output is correct
22 Correct 317 ms 102736 KB Output is correct
23 Correct 330 ms 102156 KB Output is correct
24 Correct 340 ms 102980 KB Output is correct
25 Correct 525 ms 108736 KB Output is correct
26 Correct 418 ms 109184 KB Output is correct
27 Correct 544 ms 111060 KB Output is correct
28 Correct 456 ms 107980 KB Output is correct
29 Correct 362 ms 112648 KB Output is correct
30 Correct 575 ms 118016 KB Output is correct
31 Correct 404 ms 106788 KB Output is correct
32 Correct 426 ms 110412 KB Output is correct
33 Correct 419 ms 109100 KB Output is correct
34 Correct 409 ms 107920 KB Output is correct
35 Correct 502 ms 105692 KB Output is correct
36 Correct 54 ms 76968 KB Output is correct
37 Correct 147 ms 91804 KB Output is correct
38 Correct 404 ms 107208 KB Output is correct
39 Correct 381 ms 111924 KB Output is correct
40 Correct 488 ms 112132 KB Output is correct
41 Correct 389 ms 110372 KB Output is correct
42 Correct 391 ms 107812 KB Output is correct
43 Correct 155 ms 84232 KB Output is correct
44 Correct 738 ms 113120 KB Output is correct
45 Correct 735 ms 114348 KB Output is correct
46 Correct 841 ms 119428 KB Output is correct
47 Correct 924 ms 120888 KB Output is correct
48 Correct 750 ms 118572 KB Output is correct
49 Correct 329 ms 100164 KB Output is correct
50 Correct 324 ms 112976 KB Output is correct
51 Correct 697 ms 118796 KB Output is correct
52 Correct 355 ms 108044 KB Output is correct
53 Correct 47 ms 77012 KB Output is correct
54 Correct 665 ms 114424 KB Output is correct
55 Correct 568 ms 118432 KB Output is correct
56 Correct 751 ms 120908 KB Output is correct
57 Correct 572 ms 117716 KB Output is correct
58 Correct 512 ms 113960 KB Output is correct
59 Correct 592 ms 118248 KB Output is correct
60 Correct 562 ms 117804 KB Output is correct
61 Correct 528 ms 113924 KB Output is correct
62 Correct 322 ms 99184 KB Output is correct
63 Correct 61 ms 79352 KB Output is correct
64 Correct 459 ms 110360 KB Output is correct
65 Correct 422 ms 110076 KB Output is correct
66 Correct 331 ms 106960 KB Output is correct
67 Correct 382 ms 108404 KB Output is correct
68 Correct 298 ms 106876 KB Output is correct
69 Correct 730 ms 121080 KB Output is correct
70 Correct 527 ms 118424 KB Output is correct
71 Correct 678 ms 118420 KB Output is correct
72 Correct 310 ms 100172 KB Output is correct
73 Correct 650 ms 118648 KB Output is correct
74 Correct 316 ms 107664 KB Output is correct
75 Correct 317 ms 110140 KB Output is correct
76 Correct 396 ms 109608 KB Output is correct
77 Correct 397 ms 111196 KB Output is correct
78 Correct 333 ms 108888 KB Output is correct
79 Correct 309 ms 107152 KB Output is correct
80 Correct 297 ms 111980 KB Output is correct
81 Correct 411 ms 112148 KB Output is correct
82 Correct 313 ms 110280 KB Output is correct
83 Correct 310 ms 107788 KB Output is correct
84 Correct 106 ms 83312 KB Output is correct
85 Correct 676 ms 116116 KB Output is correct
86 Correct 977 ms 130940 KB Output is correct
87 Correct 97 ms 83040 KB Output is correct
88 Correct 83 ms 82324 KB Output is correct
89 Correct 90 ms 83032 KB Output is correct
90 Correct 57 ms 78556 KB Output is correct
91 Correct 41 ms 75484 KB Output is correct
92 Correct 52 ms 77252 KB Output is correct
93 Correct 220 ms 92912 KB Output is correct
94 Correct 63 ms 79548 KB Output is correct
95 Correct 459 ms 111956 KB Output is correct
96 Correct 420 ms 110264 KB Output is correct
97 Correct 336 ms 106988 KB Output is correct
98 Correct 364 ms 108352 KB Output is correct
99 Correct 1382 ms 145680 KB Output is correct
100 Correct 649 ms 119440 KB Output is correct
101 Correct 913 ms 126844 KB Output is correct
102 Correct 323 ms 100328 KB Output is correct
103 Correct 320 ms 107728 KB Output is correct
104 Correct 327 ms 109828 KB Output is correct
105 Correct 369 ms 109448 KB Output is correct
106 Correct 331 ms 109188 KB Output is correct
107 Correct 390 ms 110864 KB Output is correct
108 Correct 66 ms 78828 KB Output is correct
109 Correct 539 ms 111320 KB Output is correct
110 Correct 565 ms 117576 KB Output is correct
111 Correct 550 ms 117712 KB Output is correct
112 Correct 382 ms 109740 KB Output is correct
113 Correct 356 ms 109160 KB Output is correct