oj.uz

답안 #1067531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1067531 2024-08-20T19:49:51 Z jamjanek Sky Walking (IOI19_walk) C++17
43 / 100
 1672 ms 109776 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*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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 21848 KB Output is correct
2 Correct 3 ms 21852 KB Output is correct
3 Correct 3 ms 21848 KB Output is correct
4 Correct 3 ms 21716 KB Output is correct
5 Correct 4 ms 21852 KB Output is correct
6 Correct 4 ms 21852 KB Output is correct
7 Correct 4 ms 21848 KB Output is correct
8 Correct 4 ms 21852 KB Output is correct
9 Correct 3 ms 21852 KB Output is correct
10 Correct 4 ms 21688 KB Output is correct
11 Correct 4 ms 21852 KB Output is correct
12 Correct 3 ms 21852 KB Output is correct
13 Correct 3 ms 21852 KB Output is correct
14 Correct 4 ms 21852 KB Output is correct
15 Correct 3 ms 21852 KB Output is correct
16 Correct 3 ms 21852 KB Output is correct
17 Correct 4 ms 21852 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 21852 KB Output is correct
2 Correct 3 ms 21852 KB Output is correct
3 Correct 643 ms 93224 KB Output is correct
4 Correct 568 ms 95588 KB Output is correct
5 Correct 370 ms 75948 KB Output is correct
6 Correct 664 ms 73392 KB Output is correct
7 Correct 336 ms 76372 KB Output is correct
8 Correct 660 ms 97484 KB Output is correct
9 Correct 519 ms 93364 KB Output is correct
10 Correct 609 ms 96544 KB Output is correct
11 Correct 533 ms 84404 KB Output is correct
12 Correct 370 ms 68532 KB Output is correct
13 Correct 624 ms 100268 KB Output is correct
14 Correct 1672 ms 67948 KB Output is correct
15 Correct 541 ms 62400 KB Output is correct
16 Correct 252 ms 61136 KB Output is correct
17 Incorrect 247 ms 59300 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 33952 KB Output is correct
2 Correct 739 ms 101636 KB Output is correct
3 Correct 835 ms 103392 KB Output is correct
4 Correct 853 ms 105788 KB Output is correct
5 Correct 845 ms 109776 KB Output is correct
6 Correct 781 ms 102228 KB Output is correct
7 Correct 337 ms 63360 KB Output is correct
8 Correct 369 ms 66448 KB Output is correct
9 Correct 689 ms 101188 KB Output is correct
10 Correct 225 ms 64492 KB Output is correct
11 Correct 12 ms 23388 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 33952 KB Output is correct
2 Correct 739 ms 101636 KB Output is correct
3 Correct 835 ms 103392 KB Output is correct
4 Correct 853 ms 105788 KB Output is correct
5 Correct 845 ms 109776 KB Output is correct
6 Correct 781 ms 102228 KB Output is correct
7 Correct 337 ms 63360 KB Output is correct
8 Correct 369 ms 66448 KB Output is correct
9 Correct 689 ms 101188 KB Output is correct
10 Correct 225 ms 64492 KB Output is correct
11 Correct 12 ms 23388 KB Output is correct
12 Correct 799 ms 104364 KB Output is correct
13 Correct 708 ms 103600 KB Output is correct
14 Correct 794 ms 109720 KB Output is correct
15 Correct 506 ms 87456 KB Output is correct
16 Correct 572 ms 88532 KB Output is correct
17 Correct 612 ms 98508 KB Output is correct
18 Correct 517 ms 86836 KB Output is correct
19 Correct 469 ms 87192 KB Output is correct
20 Correct 339 ms 62552 KB Output is correct
21 Correct 21 ms 25692 KB Output is correct
22 Correct 481 ms 88496 KB Output is correct
23 Correct 439 ms 85168 KB Output is correct
24 Correct 320 ms 70024 KB Output is correct
25 Correct 409 ms 81072 KB Output is correct
26 Correct 260 ms 63152 KB Output is correct
27 Correct 816 ms 108208 KB Output is correct
28 Correct 697 ms 102580 KB Output is correct
29 Correct 757 ms 103088 KB Output is correct
30 Correct 331 ms 63416 KB Output is correct
31 Correct 638 ms 100020 KB Output is correct
32 Correct 245 ms 61052 KB Output is correct
33 Correct 215 ms 59948 KB Output is correct
34 Correct 248 ms 66320 KB Output is correct
35 Correct 319 ms 67920 KB Output is correct
36 Correct 265 ms 62060 KB Output is correct
37 Correct 204 ms 57648 KB Output is correct
38 Correct 219 ms 56860 KB Output is correct
39 Correct 279 ms 70336 KB Output is correct
40 Correct 216 ms 57440 KB Output is correct
41 Correct 210 ms 57520 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 21848 KB Output is correct
2 Correct 3 ms 21852 KB Output is correct
3 Correct 3 ms 21848 KB Output is correct
4 Correct 3 ms 21716 KB Output is correct
5 Correct 4 ms 21852 KB Output is correct
6 Correct 4 ms 21852 KB Output is correct
7 Correct 4 ms 21848 KB Output is correct
8 Correct 4 ms 21852 KB Output is correct
9 Correct 3 ms 21852 KB Output is correct
10 Correct 4 ms 21688 KB Output is correct
11 Correct 4 ms 21852 KB Output is correct
12 Correct 3 ms 21852 KB Output is correct
13 Correct 3 ms 21852 KB Output is correct
14 Correct 4 ms 21852 KB Output is correct
15 Correct 3 ms 21852 KB Output is correct
16 Correct 3 ms 21852 KB Output is correct
17 Correct 4 ms 21852 KB Output is correct
18 Correct 3 ms 21852 KB Output is correct
19 Correct 3 ms 21852 KB Output is correct
20 Correct 643 ms 93224 KB Output is correct
21 Correct 568 ms 95588 KB Output is correct
22 Correct 370 ms 75948 KB Output is correct
23 Correct 664 ms 73392 KB Output is correct
24 Correct 336 ms 76372 KB Output is correct
25 Correct 660 ms 97484 KB Output is correct
26 Correct 519 ms 93364 KB Output is correct
27 Correct 609 ms 96544 KB Output is correct
28 Correct 533 ms 84404 KB Output is correct
29 Correct 370 ms 68532 KB Output is correct
30 Correct 624 ms 100268 KB Output is correct
31 Correct 1672 ms 67948 KB Output is correct
32 Correct 541 ms 62400 KB Output is correct
33 Correct 252 ms 61136 KB Output is correct
34 Incorrect 247 ms 59300 KB Output isn't correct
35 Halted 0 ms 0 KB -