oj.uz

Submission #1067535

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

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

const int base = 1<<17;

int drzewo[2*base];

int wiekszeL(int x, int val){
	x+=base;
	while(drzewo[x]<val && x&(x-1)){
		if(x%2==1)x/=2;
		else x--;
	}
	if(drzewo[x]>=val){
		while(x<base)
			if(drzewo[x*2+1]>=val)
				x=x*2+1;
			else
				x=x*2;
		return x-base;
	}
	else
		return -1;
}
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;
	for(i=0;i<n;i++)
		drzewo[i+base]=h[i];
	for(i=base-1;i>0;i--)
		drzewo[i]=max(drzewo[i*2], drzewo[i*2+1]);
	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 3 ms 21848 KB Output is correct
2 Correct 3 ms 21852 KB Output is correct
3 Correct 3 ms 21852 KB Output is correct
4 Correct 3 ms 21852 KB Output is correct
5 Correct 4 ms 21852 KB Output is correct
6 Correct 3 ms 21852 KB Output is correct
7 Correct 3 ms 21852 KB Output is correct
8 Correct 3 ms 21852 KB Output is correct
9 Correct 4 ms 21852 KB Output is correct
10 Correct 4 ms 21900 KB Output is correct
11 Correct 4 ms 21852 KB Output is correct
12 Correct 4 ms 21852 KB Output is correct
13 Correct 4 ms 21852 KB Output is correct
14 Correct 6 ms 21852 KB Output is correct
15 Correct 3 ms 21848 KB Output is correct
16 Correct 3 ms 21852 KB Output is correct
17 Correct 3 ms 21716 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21848 KB Output is correct
2 Correct 4 ms 21852 KB Output is correct
3 Correct 638 ms 92808 KB Output is correct
4 Correct 587 ms 92764 KB Output is correct
5 Correct 358 ms 73828 KB Output is correct
6 Correct 660 ms 71404 KB Output is correct
7 Correct 354 ms 74284 KB Output is correct
8 Correct 660 ms 94768 KB Output is correct
9 Correct 499 ms 90032 KB Output is correct
10 Correct 592 ms 94568 KB Output is correct
11 Correct 476 ms 83124 KB Output is correct
12 Correct 348 ms 66532 KB Output is correct
13 Correct 629 ms 98256 KB Output is correct
14 Correct 1642 ms 66128 KB Output is correct
15 Correct 502 ms 61992 KB Output is correct
16 Correct 242 ms 59796 KB Output is correct
17 Correct 234 ms 57556 KB Output is correct
18 Correct 292 ms 76724 KB Output is correct
19 Correct 18 ms 24260 KB Output is correct
20 Correct 361 ms 45384 KB Output is correct
21 Correct 218 ms 59636 KB Output is correct
22 Correct 214 ms 58540 KB Output is correct
23 Correct 285 ms 72244 KB Output is correct
24 Correct 218 ms 59368 KB Output is correct
25 Correct 226 ms 58852 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 33996 KB Output is correct
2 Correct 755 ms 101152 KB Output is correct
3 Correct 843 ms 103860 KB Output is correct
4 Correct 834 ms 106488 KB Output is correct
5 Correct 871 ms 109476 KB Output is correct
6 Correct 727 ms 102860 KB Output is correct
7 Correct 333 ms 63424 KB Output is correct
8 Correct 348 ms 65928 KB Output is correct
9 Correct 697 ms 101100 KB Output is correct
10 Correct 233 ms 64336 KB Output is correct
11 Correct 11 ms 23384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 33996 KB Output is correct
2 Correct 755 ms 101152 KB Output is correct
3 Correct 843 ms 103860 KB Output is correct
4 Correct 834 ms 106488 KB Output is correct
5 Correct 871 ms 109476 KB Output is correct
6 Correct 727 ms 102860 KB Output is correct
7 Correct 333 ms 63424 KB Output is correct
8 Correct 348 ms 65928 KB Output is correct
9 Correct 697 ms 101100 KB Output is correct
10 Correct 233 ms 64336 KB Output is correct
11 Correct 11 ms 23384 KB Output is correct
12 Correct 777 ms 103976 KB Output is correct
13 Correct 674 ms 103336 KB Output is correct
14 Correct 818 ms 108676 KB Output is correct
15 Correct 490 ms 87576 KB Output is correct
16 Correct 508 ms 87512 KB Output is correct
17 Correct 532 ms 98332 KB Output is correct
18 Correct 474 ms 88480 KB Output is correct
19 Correct 473 ms 89128 KB Output is correct
20 Correct 340 ms 62828 KB Output is correct
21 Correct 20 ms 25692 KB Output is correct
22 Correct 470 ms 88676 KB Output is correct
23 Correct 466 ms 85420 KB Output is correct
24 Correct 325 ms 70060 KB Output is correct
25 Correct 408 ms 81840 KB Output is correct
26 Correct 233 ms 63664 KB Output is correct
27 Correct 765 ms 108516 KB Output is correct
28 Correct 684 ms 103280 KB Output is correct
29 Correct 712 ms 103084 KB Output is correct
30 Correct 324 ms 63564 KB Output is correct
31 Correct 677 ms 100704 KB Output is correct
32 Correct 216 ms 60988 KB Output is correct
33 Correct 249 ms 60000 KB Output is correct
34 Correct 252 ms 66436 KB Output is correct
35 Correct 294 ms 67904 KB Output is correct
36 Correct 300 ms 62040 KB Output is correct
37 Correct 204 ms 57764 KB Output is correct
38 Correct 206 ms 57596 KB Output is correct
39 Correct 265 ms 70332 KB Output is correct
40 Correct 205 ms 57540 KB Output is correct
41 Correct 204 ms 57264 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21848 KB Output is correct
2 Correct 3 ms 21852 KB Output is correct
3 Correct 3 ms 21852 KB Output is correct
4 Correct 3 ms 21852 KB Output is correct
5 Correct 4 ms 21852 KB Output is correct
6 Correct 3 ms 21852 KB Output is correct
7 Correct 3 ms 21852 KB Output is correct
8 Correct 3 ms 21852 KB Output is correct
9 Correct 4 ms 21852 KB Output is correct
10 Correct 4 ms 21900 KB Output is correct
11 Correct 4 ms 21852 KB Output is correct
12 Correct 4 ms 21852 KB Output is correct
13 Correct 4 ms 21852 KB Output is correct
14 Correct 6 ms 21852 KB Output is correct
15 Correct 3 ms 21848 KB Output is correct
16 Correct 3 ms 21852 KB Output is correct
17 Correct 3 ms 21716 KB Output is correct
18 Correct 4 ms 21848 KB Output is correct
19 Correct 4 ms 21852 KB Output is correct
20 Correct 638 ms 92808 KB Output is correct
21 Correct 587 ms 92764 KB Output is correct
22 Correct 358 ms 73828 KB Output is correct
23 Correct 660 ms 71404 KB Output is correct
24 Correct 354 ms 74284 KB Output is correct
25 Correct 660 ms 94768 KB Output is correct
26 Correct 499 ms 90032 KB Output is correct
27 Correct 592 ms 94568 KB Output is correct
28 Correct 476 ms 83124 KB Output is correct
29 Correct 348 ms 66532 KB Output is correct
30 Correct 629 ms 98256 KB Output is correct
31 Correct 1642 ms 66128 KB Output is correct
32 Correct 502 ms 61992 KB Output is correct
33 Correct 242 ms 59796 KB Output is correct
34 Correct 234 ms 57556 KB Output is correct
35 Correct 292 ms 76724 KB Output is correct
36 Correct 18 ms 24260 KB Output is correct
37 Correct 361 ms 45384 KB Output is correct
38 Correct 218 ms 59636 KB Output is correct
39 Correct 214 ms 58540 KB Output is correct
40 Correct 285 ms 72244 KB Output is correct
41 Correct 218 ms 59368 KB Output is correct
42 Correct 226 ms 58852 KB Output is correct
43 Correct 69 ms 33996 KB Output is correct
44 Correct 755 ms 101152 KB Output is correct
45 Correct 843 ms 103860 KB Output is correct
46 Correct 834 ms 106488 KB Output is correct
47 Correct 871 ms 109476 KB Output is correct
48 Correct 727 ms 102860 KB Output is correct
49 Correct 333 ms 63424 KB Output is correct
50 Correct 348 ms 65928 KB Output is correct
51 Correct 697 ms 101100 KB Output is correct
52 Correct 233 ms 64336 KB Output is correct
53 Correct 11 ms 23384 KB Output is correct
54 Correct 777 ms 103976 KB Output is correct
55 Correct 674 ms 103336 KB Output is correct
56 Correct 818 ms 108676 KB Output is correct
57 Correct 490 ms 87576 KB Output is correct
58 Correct 508 ms 87512 KB Output is correct
59 Correct 532 ms 98332 KB Output is correct
60 Correct 474 ms 88480 KB Output is correct
61 Correct 473 ms 89128 KB Output is correct
62 Correct 340 ms 62828 KB Output is correct
63 Correct 20 ms 25692 KB Output is correct
64 Correct 470 ms 88676 KB Output is correct
65 Correct 466 ms 85420 KB Output is correct
66 Correct 325 ms 70060 KB Output is correct
67 Correct 408 ms 81840 KB Output is correct
68 Correct 233 ms 63664 KB Output is correct
69 Correct 765 ms 108516 KB Output is correct
70 Correct 684 ms 103280 KB Output is correct
71 Correct 712 ms 103084 KB Output is correct
72 Correct 324 ms 63564 KB Output is correct
73 Correct 677 ms 100704 KB Output is correct
74 Correct 216 ms 60988 KB Output is correct
75 Correct 249 ms 60000 KB Output is correct
76 Correct 252 ms 66436 KB Output is correct
77 Correct 294 ms 67904 KB Output is correct
78 Correct 300 ms 62040 KB Output is correct
79 Correct 204 ms 57764 KB Output is correct
80 Correct 206 ms 57596 KB Output is correct
81 Correct 265 ms 70332 KB Output is correct
82 Correct 205 ms 57540 KB Output is correct
83 Correct 204 ms 57264 KB Output is correct
84 Correct 79 ms 32088 KB Output is correct
85 Correct 791 ms 107136 KB Output is correct
86 Correct 893 ms 126116 KB Output is correct
87 Correct 42 ms 31568 KB Output is correct
88 Correct 43 ms 31648 KB Output is correct
89 Correct 44 ms 31564 KB Output is correct
90 Correct 19 ms 25620 KB Output is correct
91 Correct 4 ms 21852 KB Output is correct
92 Correct 21 ms 24924 KB Output is correct
93 Correct 243 ms 52064 KB Output is correct
94 Correct 22 ms 26964 KB Output is correct
95 Correct 505 ms 91992 KB Output is correct
96 Correct 528 ms 86960 KB Output is correct
97 Correct 938 ms 72892 KB Output is correct
98 Correct 427 ms 83844 KB Output is correct
99 Correct 1132 ms 143488 KB Output is correct
100 Correct 752 ms 105720 KB Output is correct
101 Correct 799 ms 117180 KB Output is correct
102 Correct 305 ms 63548 KB Output is correct
103 Correct 215 ms 61108 KB Output is correct
104 Correct 205 ms 59948 KB Output is correct
105 Correct 248 ms 66488 KB Output is correct
106 Correct 345 ms 63484 KB Output is correct
107 Correct 361 ms 66572 KB Output is correct
108 Correct 39 ms 27912 KB Output is correct
109 Correct 541 ms 88216 KB Output is correct
110 Correct 653 ms 104180 KB Output is correct
111 Correct 631 ms 103604 KB Output is correct
112 Correct 284 ms 66756 KB Output is correct
113 Correct 289 ms 64952 KB Output is correct