oj.uz

Submission #1067523

# Submission time Handle Problem Language Result Execution time Memory
1067523 2024-08-20T19:40:40 Z jamjanek Sky Walking (IOI19_walk) C++17
100 / 100
 2025 ms 145676 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;

vector<int>l,r,y,x,h;

const int base = 1<<17;


int wiekszeL(int x, int val){
	while(x>=0){
		if(h[x]>=val)break;
		x--;
	}
	return x;
}
int wiekszeR(int x, int val){
	while(x<(int)h.size()){
		if(h[x]>=val)break;
		x++;
	}
	return x;
}


int tree[2*base];
void ustaw(int w, int l, int p, int a, int b, int v){
	if(a<=l && p<=b){
		tree[w] = v;
		return;
	}
	if(b<l || p<a)return;
	if(tree[w]!=-1)
		tree[w*2] = tree[w*2+1] = tree[w];
	ustaw(w*2, l, (l+p)/2, a, b, v);
	ustaw(w*2+1, (l+p)/2+1, p, a, b, v);
	tree[w] = -1;
}
int odczyt(int w){
	int res = -1;
	w+=base;
	while(w>0){
		if(tree[w]!=-1)
			res = tree[w];
		w/=2;
	}
	return res;
}

void dodaj(int a, int b, int h){
	l.push_back(a);
	r.push_back(b);
	y.push_back(h);
}
vector<pair<int,long long>>graf[700010];
long long dist[700010];
bool odw[700010];
map<pair<int,int>,int>mapa;
long long odl(pair<int,int>a, pair<int,int>b){
	return abs(a.second-b.second);
}
long long odl1(pair<int,int>a, pair<int,int>b){
	return abs(x[a.first]-x[b.first]);
}
map<int,vector<pair<int,int>>>poziomy;
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int s, int g) {
	x = X;
	h = H;
	// podzielic kazda pozioma
	// dla kazdej poziomej wyznaczyc pozioma w dol z obu koncy
	vector<tuple<int,int,int,int>>przedzialy;
	int n = x.size();
	int m = L.size();
	int i;
	if(s>g)swap(s,g);
	for(i=0;i<m;i++){
		poziomy[Y[i]].push_back({L[i],R[i]});
		if(L[i]<s && R[i]>g){
//			printf("%d 3\n", i);
			dodaj(L[i],s,Y[i]);
			dodaj(s,g,Y[i]);
			dodaj(g,R[i],Y[i]);
		}
		else if(L[i]<s && R[i]>s){
//			printf("%d 2\n", i);
			dodaj(L[i],s,Y[i]);
			dodaj(s,R[i],Y[i]);
		}
		else if(g<R[i] && L[i]<g){
//			printf("%d 2\n", i);
			dodaj(L[i],g,Y[i]);
			dodaj(g,R[i],Y[i]);
		}
		else{
//			printf("%d 1\n");
			dodaj(L[i],R[i],Y[i]);
		}
	}
	m = l.size();
	//for(i=0;i<m;i++)printf("%d %d %d %d\n", y[i], l[i], r[i], i);printf("\n");
	for(i=0;i<m;i++)
		przedzialy.push_back({y[i],l[i],r[i],0});
	sort(przedzialy.begin(), przedzialy.end());
	for(i=0;i<m;i++)
		get<3>(przedzialy[i]) = i;
	for(i=0;i<n;i++)tree[i+base] = -1;
	for(i=base-1;i>0;i--)
		tree[i] = -1;
	ustaw(1, 0,base-1,s,s,0);
	ustaw(1, 0,base-1,g,g,0);
	mapa[{s,0}]=0;
	mapa[{g,0}]=1;
	for(auto j: przedzialy){
		auto [Y,L,R,i] = j;
		int a = wiekszeR(L, Y);
		if(a<=R){
			int b = odczyt(a);
			if(b!=-1 && mapa.find({a, b})==mapa.end())
				mapa[{a,b}] = mapa.size();
			if(mapa.find({a, Y})==mapa.end())
				mapa[{a,Y}] = mapa.size();
		}
		a = wiekszeL(R,Y);
		if(a>=L){
			int b = odczyt(a);
			if(b!=-1 &&mapa.find({a, b})==mapa.end())
				mapa[{a,b}] = mapa.size();
			if(mapa.find({a, Y})==mapa.end())
				mapa[{a,Y}] = mapa.size();
		}
		ustaw(1, 0, base-1, L, R, Y);

/*
		for(int ij=0;ij<2;ij++){
			int a = odczyt(ij?R:L);
			int s = (a-2)/2;
			b = i*2+2+ij;
//			if(ij==0)printf("LEWY: %d %d(%d)\n", b, a,s);
//			else printf("PRAWY: %d %d(%d)\n", b, a,s);
			if(a==-1)continue;
			if(a==0 || a==1){
				graf[b].push_back({a,Y});
				graf[a].push_back({b,Y});
			}
			else{
				long long d;
				d=Y-get<0>(przedzialy[s])+abs(x[ij?R:L]-x[get<1>(przedzialy[s])]);
				graf[b].push_back({a, d});
				graf[a].push_back({b, d});
				d=Y-get<0>(przedzialy[s])+abs(x[ij?R:L]-x[get<2>(przedzialy[s])]);
				graf[b].push_back({a^1, d});
				graf[a^1].push_back({b, d});
				
			}
		}
		
		graf[b].push_back({b-1, abs(x[L]-x[R])});
		graf[b-1].push_back({b, abs(x[L]-x[R])});
		ustaw(1, 0, base-1, L, R, b-1);*/
//		printf("%d %d %d: %d %d\n", y[i], l[i], r[i], b-1, b);
	}/*
	for(i=0;i<(int)przedzialy.size()*2+2;i++){
		printf("%d: ", i);
		for(auto j: graf[i])
			printf("%d-%d ", j.first, j.second);
		printf("\n");
	}*/
	vector<pair<pair<int,int>,int>>wartosci;
	for(auto j=mapa.begin();j!=mapa.end();j++){
		auto xd = *j;
		wartosci.push_back({xd.first, xd.second});
		auto next = j;
		next++;
		if(next==mapa.end())break;
		if((*next).first.first==(*j).first.first){
			graf[(*next).second].push_back({(*j).second, odl((*j).first, (*next).first)});
			graf[(*j).second].push_back({(*next).second, odl((*j).first, (*next).first)});
		}
	}


	for(auto &j: poziomy){
		auto &vec = j.second;
		vector<pair<int,int>>dobre;
		sort(vec.begin(), vec.end());
		int koniec = (*vec.begin()).second, pocz = (*vec.begin()).first;
		for(auto k: vec){
			if(k.first<=koniec)
				koniec = max(k.second, koniec);
			else{
//				printf("%d %d\n", pocz, koniec);
				dobre.push_back({pocz, koniec});
				pocz = k.first;
				koniec = k.second;
			}
		}
		dobre.push_back({pocz,koniec});
//		for(auto ij: vec)printf("%d %d, ", ij.first, ij.second);printf("dsad\n");
		vec = dobre;
//		for(auto ij: dobre)printf("%d %d, ", ij.first, ij.second);printf("\n");
	}
		
	mapa.clear();
	for(auto j:wartosci)
		mapa[{j.first.second,j.first.first}]=j.second;



	for(auto j=mapa.begin();j!=mapa.end();j++){
		if((*j).first.first==0)continue;
		auto next = j;
		next++;
		if(next==mapa.end())break;
		if((*next).first.first==(*j).first.first){
			int a =(*j).first.second, b = (*next).first.second;
			auto &pom = poziomy[(*j).first.first];
			if(upper_bound(pom.begin(), pom.end(), make_pair(a,1000000000))==upper_bound(pom.begin(), pom.end(), make_pair(b,1000000000))){
				graf[(*next).second].push_back({(*j).second, x[(*next).first.second]-x[(*j).first.second]});
				graf[(*j).second].push_back({(*next).second, x[(*next).first.second]-x[(*j).first.second]});
			}
		}
	}/*
	for(auto j: wartosci)printf("%d %d %d\n", j.second, j.first.first, j.first.second);
	for(i=0;i<10;i++){
		printf("%d: ", i);
		for(auto j: graf[i])printf("%d-%d ", j.first,j.second);printf("\n");
	}*/
	priority_queue<pair<long long, int>>kolejka;
	dist[0] = 1;
	kolejka.push({-1,0});
	while(kolejka.size()){
		auto a = kolejka.top();
		//printf("%lld %d %d\n", -a.first, a.second);
		kolejka.pop();
		if(odw[a.second])continue;
		odw[a.second]=1;
		for(auto j: graf[a.second]){
			if(dist[j.first]==0 || dist[j.first]>dist[a.second]+j.second){
				dist[j.first]=dist[a.second]+j.second;
				kolejka.push({-dist[j.first], j.first});
			}
		}
	}
	return dist[1]-1;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17244 KB Output is correct
2 Correct 7 ms 17244 KB Output is correct
3 Correct 7 ms 17244 KB Output is correct
4 Correct 7 ms 17244 KB Output is correct
5 Correct 7 ms 17240 KB Output is correct
6 Correct 7 ms 17244 KB Output is correct
7 Correct 7 ms 17244 KB Output is correct
8 Correct 7 ms 17244 KB Output is correct
9 Correct 8 ms 17244 KB Output is correct
10 Correct 7 ms 17244 KB Output is correct
11 Correct 7 ms 17244 KB Output is correct
12 Correct 7 ms 17240 KB Output is correct
13 Correct 7 ms 17240 KB Output is correct
14 Correct 8 ms 17244 KB Output is correct
15 Correct 10 ms 17244 KB Output is correct
16 Correct 7 ms 17272 KB Output is correct
17 Correct 7 ms 17240 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17244 KB Output is correct
2 Correct 9 ms 17316 KB Output is correct
3 Correct 685 ms 91192 KB Output is correct
4 Correct 576 ms 93360 KB Output is correct
5 Correct 362 ms 72676 KB Output is correct
6 Correct 696 ms 70064 KB Output is correct
7 Correct 348 ms 73656 KB Output is correct
8 Correct 710 ms 93996 KB Output is correct
9 Correct 504 ms 90088 KB Output is correct
10 Correct 601 ms 95148 KB Output is correct
11 Correct 483 ms 82352 KB Output is correct
12 Correct 399 ms 66724 KB Output is correct
13 Correct 606 ms 97700 KB Output is correct
14 Correct 2025 ms 64420 KB Output is correct
15 Correct 671 ms 60456 KB Output is correct
16 Correct 226 ms 59052 KB Output is correct
17 Correct 229 ms 56908 KB Output is correct
18 Correct 281 ms 74620 KB Output is correct
19 Correct 22 ms 19952 KB Output is correct
20 Correct 535 ms 42168 KB Output is correct
21 Correct 224 ms 57136 KB Output is correct
22 Correct 205 ms 56568 KB Output is correct
23 Correct 286 ms 70144 KB Output is correct
24 Correct 213 ms 57172 KB Output is correct
25 Correct 218 ms 56752 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 30560 KB Output is correct
2 Correct 720 ms 99568 KB Output is correct
3 Correct 860 ms 102808 KB Output is correct
4 Correct 848 ms 106580 KB Output is correct
5 Correct 912 ms 109556 KB Output is correct
6 Correct 718 ms 103344 KB Output is correct
7 Correct 344 ms 63320 KB Output is correct
8 Correct 347 ms 66740 KB Output is correct
9 Correct 688 ms 100012 KB Output is correct
10 Correct 237 ms 64376 KB Output is correct
11 Correct 17 ms 19584 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 30560 KB Output is correct
2 Correct 720 ms 99568 KB Output is correct
3 Correct 860 ms 102808 KB Output is correct
4 Correct 848 ms 106580 KB Output is correct
5 Correct 912 ms 109556 KB Output is correct
6 Correct 718 ms 103344 KB Output is correct
7 Correct 344 ms 63320 KB Output is correct
8 Correct 347 ms 66740 KB Output is correct
9 Correct 688 ms 100012 KB Output is correct
10 Correct 237 ms 64376 KB Output is correct
11 Correct 17 ms 19584 KB Output is correct
12 Correct 816 ms 102316 KB Output is correct
13 Correct 696 ms 102056 KB Output is correct
14 Correct 781 ms 109388 KB Output is correct
15 Correct 479 ms 87072 KB Output is correct
16 Correct 457 ms 88216 KB Output is correct
17 Correct 510 ms 98528 KB Output is correct
18 Correct 475 ms 86940 KB Output is correct
19 Correct 465 ms 88264 KB Output is correct
20 Correct 339 ms 62184 KB Output is correct
21 Correct 24 ms 22656 KB Output is correct
22 Correct 499 ms 86956 KB Output is correct
23 Correct 431 ms 84464 KB Output is correct
24 Correct 336 ms 69300 KB Output is correct
25 Correct 407 ms 79676 KB Output is correct
26 Correct 286 ms 61876 KB Output is correct
27 Correct 733 ms 108976 KB Output is correct
28 Correct 657 ms 101696 KB Output is correct
29 Correct 690 ms 103084 KB Output is correct
30 Correct 322 ms 63212 KB Output is correct
31 Correct 612 ms 100008 KB Output is correct
32 Correct 212 ms 60728 KB Output is correct
33 Correct 219 ms 59944 KB Output is correct
34 Correct 258 ms 66252 KB Output is correct
35 Correct 293 ms 67652 KB Output is correct
36 Correct 272 ms 61812 KB Output is correct
37 Correct 206 ms 57316 KB Output is correct
38 Correct 206 ms 56636 KB Output is correct
39 Correct 254 ms 70008 KB Output is correct
40 Correct 203 ms 57292 KB Output is correct
41 Correct 226 ms 56748 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17244 KB Output is correct
2 Correct 7 ms 17244 KB Output is correct
3 Correct 7 ms 17244 KB Output is correct
4 Correct 7 ms 17244 KB Output is correct
5 Correct 7 ms 17240 KB Output is correct
6 Correct 7 ms 17244 KB Output is correct
7 Correct 7 ms 17244 KB Output is correct
8 Correct 7 ms 17244 KB Output is correct
9 Correct 8 ms 17244 KB Output is correct
10 Correct 7 ms 17244 KB Output is correct
11 Correct 7 ms 17244 KB Output is correct
12 Correct 7 ms 17240 KB Output is correct
13 Correct 7 ms 17240 KB Output is correct
14 Correct 8 ms 17244 KB Output is correct
15 Correct 10 ms 17244 KB Output is correct
16 Correct 7 ms 17272 KB Output is correct
17 Correct 7 ms 17240 KB Output is correct
18 Correct 7 ms 17244 KB Output is correct
19 Correct 9 ms 17316 KB Output is correct
20 Correct 685 ms 91192 KB Output is correct
21 Correct 576 ms 93360 KB Output is correct
22 Correct 362 ms 72676 KB Output is correct
23 Correct 696 ms 70064 KB Output is correct
24 Correct 348 ms 73656 KB Output is correct
25 Correct 710 ms 93996 KB Output is correct
26 Correct 504 ms 90088 KB Output is correct
27 Correct 601 ms 95148 KB Output is correct
28 Correct 483 ms 82352 KB Output is correct
29 Correct 399 ms 66724 KB Output is correct
30 Correct 606 ms 97700 KB Output is correct
31 Correct 2025 ms 64420 KB Output is correct
32 Correct 671 ms 60456 KB Output is correct
33 Correct 226 ms 59052 KB Output is correct
34 Correct 229 ms 56908 KB Output is correct
35 Correct 281 ms 74620 KB Output is correct
36 Correct 22 ms 19952 KB Output is correct
37 Correct 535 ms 42168 KB Output is correct
38 Correct 224 ms 57136 KB Output is correct
39 Correct 205 ms 56568 KB Output is correct
40 Correct 286 ms 70144 KB Output is correct
41 Correct 213 ms 57172 KB Output is correct
42 Correct 218 ms 56752 KB Output is correct
43 Correct 63 ms 30560 KB Output is correct
44 Correct 720 ms 99568 KB Output is correct
45 Correct 860 ms 102808 KB Output is correct
46 Correct 848 ms 106580 KB Output is correct
47 Correct 912 ms 109556 KB Output is correct
48 Correct 718 ms 103344 KB Output is correct
49 Correct 344 ms 63320 KB Output is correct
50 Correct 347 ms 66740 KB Output is correct
51 Correct 688 ms 100012 KB Output is correct
52 Correct 237 ms 64376 KB Output is correct
53 Correct 17 ms 19584 KB Output is correct
54 Correct 816 ms 102316 KB Output is correct
55 Correct 696 ms 102056 KB Output is correct
56 Correct 781 ms 109388 KB Output is correct
57 Correct 479 ms 87072 KB Output is correct
58 Correct 457 ms 88216 KB Output is correct
59 Correct 510 ms 98528 KB Output is correct
60 Correct 475 ms 86940 KB Output is correct
61 Correct 465 ms 88264 KB Output is correct
62 Correct 339 ms 62184 KB Output is correct
63 Correct 24 ms 22656 KB Output is correct
64 Correct 499 ms 86956 KB Output is correct
65 Correct 431 ms 84464 KB Output is correct
66 Correct 336 ms 69300 KB Output is correct
67 Correct 407 ms 79676 KB Output is correct
68 Correct 286 ms 61876 KB Output is correct
69 Correct 733 ms 108976 KB Output is correct
70 Correct 657 ms 101696 KB Output is correct
71 Correct 690 ms 103084 KB Output is correct
72 Correct 322 ms 63212 KB Output is correct
73 Correct 612 ms 100008 KB Output is correct
74 Correct 212 ms 60728 KB Output is correct
75 Correct 219 ms 59944 KB Output is correct
76 Correct 258 ms 66252 KB Output is correct
77 Correct 293 ms 67652 KB Output is correct
78 Correct 272 ms 61812 KB Output is correct
79 Correct 206 ms 57316 KB Output is correct
80 Correct 206 ms 56636 KB Output is correct
81 Correct 254 ms 70008 KB Output is correct
82 Correct 203 ms 57292 KB Output is correct
83 Correct 226 ms 56748 KB Output is correct
84 Correct 58 ms 28104 KB Output is correct
85 Correct 880 ms 104884 KB Output is correct
86 Correct 938 ms 124828 KB Output is correct
87 Correct 45 ms 28024 KB Output is correct
88 Correct 48 ms 27824 KB Output is correct
89 Correct 45 ms 27980 KB Output is correct
90 Correct 23 ms 21004 KB Output is correct
91 Correct 8 ms 17500 KB Output is correct
92 Correct 22 ms 20532 KB Output is correct
93 Correct 207 ms 49528 KB Output is correct
94 Correct 25 ms 22872 KB Output is correct
95 Correct 534 ms 90036 KB Output is correct
96 Correct 499 ms 83740 KB Output is correct
97 Correct 1006 ms 69776 KB Output is correct
98 Correct 404 ms 79532 KB Output is correct
99 Correct 1121 ms 145676 KB Output is correct
100 Correct 782 ms 106580 KB Output is correct
101 Correct 819 ms 116392 KB Output is correct
102 Correct 315 ms 65628 KB Output is correct
103 Correct 207 ms 63232 KB Output is correct
104 Correct 215 ms 62152 KB Output is correct
105 Correct 250 ms 68544 KB Output is correct
106 Correct 459 ms 65992 KB Output is correct
107 Correct 466 ms 68536 KB Output is correct
108 Correct 39 ms 27896 KB Output is correct
109 Correct 603 ms 90548 KB Output is correct
110 Correct 657 ms 107456 KB Output is correct
111 Correct 642 ms 107112 KB Output is correct
112 Correct 281 ms 69048 KB Output is correct
113 Correct 304 ms 66996 KB Output is correct