oj.uz

Submission #1067530

# Submission time Handle Problem Language Result Execution time Memory
1067530 2024-08-20T19:49:09 Z jamjanek Sky Walking (IOI19_walk) C++17
33 / 100
 4000 ms 111936 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-11)){
		if(x%2==1)x/=2;
		else x--;
	}
	if(drzewo[x]>=val){
		while(x<base)
			if(drzewo[x*2+1]>=val)
				x=x*+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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21852 KB Output is correct
2 Correct 3 ms 21852 KB Output is correct
3 Correct 3 ms 21728 KB Output is correct
4 Correct 3 ms 21848 KB Output is correct
5 Correct 3 ms 21852 KB Output is correct
6 Correct 4 ms 21680 KB Output is correct
7 Execution timed out 4083 ms 19804 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
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 Execution timed out 4078 ms 55844 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 34500 KB Output is correct
2 Correct 711 ms 103088 KB Output is correct
3 Correct 772 ms 106176 KB Output is correct
4 Correct 759 ms 107876 KB Output is correct
5 Correct 777 ms 111572 KB Output is correct
6 Correct 698 ms 106400 KB Output is correct
7 Correct 326 ms 65308 KB Output is correct
8 Correct 348 ms 68620 KB Output is correct
9 Correct 637 ms 101792 KB Output is correct
10 Correct 244 ms 66488 KB Output is correct
11 Correct 11 ms 24152 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 34500 KB Output is correct
2 Correct 711 ms 103088 KB Output is correct
3 Correct 772 ms 106176 KB Output is correct
4 Correct 759 ms 107876 KB Output is correct
5 Correct 777 ms 111572 KB Output is correct
6 Correct 698 ms 106400 KB Output is correct
7 Correct 326 ms 65308 KB Output is correct
8 Correct 348 ms 68620 KB Output is correct
9 Correct 637 ms 101792 KB Output is correct
10 Correct 244 ms 66488 KB Output is correct
11 Correct 11 ms 24152 KB Output is correct
12 Correct 798 ms 104360 KB Output is correct
13 Correct 684 ms 105148 KB Output is correct
14 Correct 790 ms 111936 KB Output is correct
15 Correct 511 ms 88732 KB Output is correct
16 Correct 482 ms 90748 KB Output is correct
17 Correct 532 ms 99776 KB Output is correct
18 Correct 513 ms 90456 KB Output is correct
19 Correct 450 ms 90008 KB Output is correct
20 Correct 319 ms 64188 KB Output is correct
21 Correct 21 ms 26972 KB Output is correct
22 Correct 464 ms 89308 KB Output is correct
23 Correct 413 ms 88468 KB Output is correct
24 Correct 311 ms 72068 KB Output is correct
25 Correct 401 ms 84020 KB Output is correct
26 Correct 241 ms 65204 KB Output is correct
27 Correct 765 ms 110548 KB Output is correct
28 Correct 644 ms 105984 KB Output is correct
29 Correct 718 ms 106096 KB Output is correct
30 Correct 310 ms 65216 KB Output is correct
31 Correct 609 ms 101900 KB Output is correct
32 Correct 209 ms 62840 KB Output is correct
33 Correct 246 ms 61780 KB Output is correct
34 Correct 241 ms 68280 KB Output is correct
35 Correct 296 ms 69496 KB Output is correct
36 Correct 257 ms 64316 KB Output is correct
37 Correct 198 ms 59548 KB Output is correct
38 Correct 210 ms 58724 KB Output is correct
39 Correct 260 ms 72120 KB Output is correct
40 Correct 200 ms 59420 KB Output is correct
41 Correct 210 ms 58796 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21852 KB Output is correct
2 Correct 3 ms 21852 KB Output is correct
3 Correct 3 ms 21728 KB Output is correct
4 Correct 3 ms 21848 KB Output is correct
5 Correct 3 ms 21852 KB Output is correct
6 Correct 4 ms 21680 KB Output is correct
7 Execution timed out 4083 ms 19804 KB Time limit exceeded
8 Halted 0 ms 0 KB -