oj.uz

Submission #1067520

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

const int base = 1<<17;
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;
}

vector<int>l,r,y,x;
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;
	// 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 = odczyt(L);
		if(a!=-1 && mapa.find({L, a})==mapa.end())
			mapa[{L,a}] = mapa.size();
		a = odczyt(R);
		if(a!=-1 &&mapa.find({R, a})==mapa.end())
			mapa[{R,a}] = mapa.size();
		if(mapa.find({R, Y})==mapa.end())
			mapa[{R,Y}] = mapa.size();
		if(mapa.find({L, Y})==mapa.end())
			mapa[{L,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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 17496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 17244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 30408 KB Output is correct
2 Correct 688 ms 99756 KB Output is correct
3 Correct 794 ms 102572 KB Output is correct
4 Correct 770 ms 106160 KB Output is correct
5 Correct 770 ms 109224 KB Output is correct
6 Correct 693 ms 102932 KB Output is correct
7 Correct 322 ms 62908 KB Output is correct
8 Correct 341 ms 66224 KB Output is correct
9 Correct 656 ms 99708 KB Output is correct
10 Correct 241 ms 64052 KB Output is correct
11 Correct 16 ms 19200 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 30408 KB Output is correct
2 Correct 688 ms 99756 KB Output is correct
3 Correct 794 ms 102572 KB Output is correct
4 Correct 770 ms 106160 KB Output is correct
5 Correct 770 ms 109224 KB Output is correct
6 Correct 693 ms 102932 KB Output is correct
7 Correct 322 ms 62908 KB Output is correct
8 Correct 341 ms 66224 KB Output is correct
9 Correct 656 ms 99708 KB Output is correct
10 Correct 241 ms 64052 KB Output is correct
11 Correct 16 ms 19200 KB Output is correct
12 Correct 790 ms 102444 KB Output is correct
13 Correct 669 ms 101544 KB Output is correct
14 Correct 774 ms 108968 KB Output is correct
15 Correct 547 ms 86652 KB Output is correct
16 Correct 494 ms 87708 KB Output is correct
17 Correct 566 ms 97952 KB Output is correct
18 Correct 552 ms 86744 KB Output is correct
19 Correct 528 ms 87872 KB Output is correct
20 Correct 372 ms 61632 KB Output is correct
21 Correct 27 ms 22352 KB Output is correct
22 Correct 512 ms 86612 KB Output is correct
23 Correct 490 ms 84012 KB Output is correct
24 Correct 354 ms 68696 KB Output is correct
25 Correct 451 ms 79108 KB Output is correct
26 Correct 263 ms 61400 KB Output is correct
27 Correct 836 ms 108736 KB Output is correct
28 Correct 687 ms 101152 KB Output is correct
29 Correct 768 ms 102876 KB Output is correct
30 Correct 336 ms 62772 KB Output is correct
31 Correct 643 ms 99652 KB Output is correct
32 Correct 219 ms 60472 KB Output is correct
33 Correct 209 ms 59644 KB Output is correct
34 Correct 254 ms 65776 KB Output is correct
35 Correct 276 ms 67276 KB Output is correct
36 Correct 250 ms 61368 KB Output is correct
37 Correct 203 ms 56880 KB Output is correct
38 Correct 206 ms 56156 KB Output is correct
39 Correct 286 ms 69556 KB Output is correct
40 Correct 197 ms 56772 KB Output is correct
41 Correct 207 ms 56496 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 17496 KB Output isn't correct
2 Halted 0 ms 0 KB -