oj.uz

Submission #1067413

# Submission time Handle Problem Language Result Execution time Memory
1067413 2024-08-20T16:42:57 Z jamjanek Sky Walking (IOI19_walk) C++17
15 / 100
 173 ms 56896 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;
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];
long long min_distance(vector<int> x, vector<int> h, vector<int> L, vector<int> R, vector<int> Y, int s, int g) {
	// 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++){
		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,1);
	for(auto j: przedzialy){
		auto [Y,L,R,i] = j;
		int b;
		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");
	}*/
	priority_queue<pair<long long, int>>kolejka;
	dist[0] = 1;
	kolejka.push({-1,0});
	while(kolejka.size()){
		auto a = kolejka.top();
		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 17244 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 46 ms 33356 KB Output is correct
2 Correct 127 ms 49848 KB Output is correct
3 Correct 138 ms 50332 KB Output is correct
4 Correct 166 ms 53956 KB Output is correct
5 Correct 173 ms 56132 KB Output is correct
6 Correct 169 ms 56644 KB Output is correct
7 Correct 81 ms 39172 KB Output is correct
8 Correct 118 ms 45376 KB Output is correct
9 Correct 158 ms 56644 KB Output is correct
10 Correct 105 ms 52380 KB Output is correct
11 Correct 13 ms 19032 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 33356 KB Output is correct
2 Correct 127 ms 49848 KB Output is correct
3 Correct 138 ms 50332 KB Output is correct
4 Correct 166 ms 53956 KB Output is correct
5 Correct 173 ms 56132 KB Output is correct
6 Correct 169 ms 56644 KB Output is correct
7 Correct 81 ms 39172 KB Output is correct
8 Correct 118 ms 45376 KB Output is correct
9 Correct 158 ms 56644 KB Output is correct
10 Correct 105 ms 52380 KB Output is correct
11 Correct 13 ms 19032 KB Output is correct
12 Correct 135 ms 50240 KB Output is correct
13 Correct 111 ms 51776 KB Output is correct
14 Correct 165 ms 55956 KB Output is correct
15 Correct 111 ms 48704 KB Output is correct
16 Correct 135 ms 56896 KB Output is correct
17 Correct 130 ms 55352 KB Output is correct
18 Correct 114 ms 48708 KB Output is correct
19 Correct 130 ms 56388 KB Output is correct
20 Incorrect 88 ms 37452 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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