oj.uz

Submission #803084

# Submission time Handle Problem Language Result Execution time Memory
803084 2023-08-02T21:24:52 Z APROHACK Sky Walking (IOI19_walk) C++17
24 / 100
 2584 ms 1017976 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
struct skywalk{
	ll l, r, y;
};
vector<pair<ll, ll>>buildings;
vector<skywalk>skywalks;
map<pair<ll, ll>, ll>intersecciones;
vector<pair<ll, ll>>puntosEnB[100005]; // los puntos de cada building
// la memoria se podria optimizar.

ll puntoCur = 0;
vector<pair<ll, ll> >adj[3000000]; // distancia, nodo
int n, m;
vector<pair<ll, ll>>corresponde;

ll generateinterseccion(ll build, ll y){
	if(intersecciones.count({buildings[build].ff, y})==1)return intersecciones[{buildings[build].ff, y}];
	corresponde.pb({buildings[build].ff, y});
	puntosEnB[build].pb({buildings[build].ff, y});
	intersecciones[{buildings[build].ff, y}] = puntoCur ++;
	return puntoCur - 1;
}
void unir(ll a, ll b, ll distancia){
	distancia = abs(distancia);
	adj[a].pb({distancia, b});
	adj[b].pb({distancia, a});
}
struct segTree{
	pair<int, int>val; // val, pos
	int dd, ht, mid;
	segTree *L, *R;
	segTree(int l, int r){
		dd = l;
		ht = r;
		mid = (dd + ht)/2;
		if(dd != ht){
			L = new segTree (l, mid);
			R = new segTree (mid+1, r);
			val = max(L->val, R->val);
		}else val = {buildings[dd].ss, dd};
	}
	pair<int, int > query(int l, int r){
		if( l == dd and r == ht)return val;
		if( r <= mid) return L->query(l, r);
		else if(mid < l )return R->query(l, r);
		else return max(L->query(l, mid), R->query(mid+1, r));
	}
};
segTree *maximos;

vector<ll>inter;
void getInter(ll l, ll r, ll y){
	//cout << "ask " << l << " " << r << endl;
	if(l > r) return ;
	pair<ll, ll > maxi = maximos->query(l, r);
	if(maxi.ff < y)return ;
	inter.pb(maxi.ss);
	getInter(l, maxi.ss-1, y);
	getInter(maxi.ss + 1, r, y);
}


void getI(ll l, ll r, ll y){
	ll anterior = generateinterseccion(l, y), actual;
	ll antX = buildings[l].ff;
	
	getInter(l+1, r, y);
	sort(inter.begin(), inter.end());
	for(auto i : inter){
		actual = generateinterseccion(i, y);
		unir(anterior, actual, buildings[i].ff - antX);
		anterior = actual;
		antX = buildings[i].ff;
	}
	inter.clear();
}

ll dijkstra(ll s, ll g){
	priority_queue<pair<ll, ll>>pq;
	pq.push({0, s});
	ll distancias[puntoCur+1];
	for(ll i = 0 ; i < puntoCur ; i ++){
		distancias[i] = LLONG_MAX;
	}
	distancias[s] = 0;
	while(!pq.empty()){
		pair<ll, ll>cur = pq.top();
		pq.pop();
		cur.ff = -cur.ff;
		if(cur.ss == g)break;
		if(distancias[cur.ss] < cur.ff)continue;
		//cout << "arrived " << cur.ss << endl;
		for(ll i = 0 ; i < adj[cur.ss].size() ; i ++){
			auto nxt = adj[cur.ss][i];
			//cout << "can go " << corresponde[nxt.ss].ff << ", " << corresponde[nxt.ss].ss << endl;
			//cout << nxt.ff + cur.ff << " < " << distancias[nxt.ss] << endl; 
			if(nxt.ff + cur.ff < distancias[nxt.ss]){
				distancias[nxt.ss] = nxt.ff + cur.ff;
				pq.push({-distancias[nxt.ss], nxt.ss});
			}
		}
	}
	if(distancias[g] == LLONG_MAX)distancias[g] = -1;
	return distancias[g];
}

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	n = x.size();
	m = l.size();
	for(ll i = 0 ; i < n ; i ++){
		buildings.pb({x[i], h[i]});
	}
	maximos = new segTree(0, n-1);
	for(ll i = 0 ; i < m ; i ++){
		skywalks.pb({l[i], r[i], y[i]});
	}
	for(ll i = 0 ; i < n ; i ++){
		generateinterseccion(i, 0);
		//puntosEnB[i].pb({x[i], 0});
		//intersecciones[{x[i], 0}] = puntoCur++;
	}
	for(ll i = 0 ; i < m ; i++){
		getI(l[i], r[i], y[i]);
	}
	for(ll i = 0 ; i < n ; i ++){
		sort(puntosEnB[i].begin(), puntosEnB[i].end());
		for (ll j = 1 ; j < puntosEnB[i].size() ; j ++){
			unir(intersecciones[puntosEnB[i][j-1]], intersecciones[puntosEnB[i][j]], puntosEnB[i][j].ss - puntosEnB[i][j-1].ss);
		}
	}
	//for(ll i = 0 ; i < puntoCur ; i ++){
	//	cout << i << " = " << corresponde[i].ff << ", " << corresponde[i].ss << endl;
	//}
	return dijkstra(intersecciones[{x[s], 0}], intersecciones[{x[g], 0}]);
}

Compilation message

walk.cpp: In function 'long long int dijkstra(long long int, long long int)':
walk.cpp:99:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(ll i = 0 ; i < adj[cur.ss].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:133:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (ll j = 1 ; j < puntosEnB[i].size() ; j ++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 73044 KB Output is correct
2 Correct 35 ms 73032 KB Output is correct
3 Correct 35 ms 73044 KB Output is correct
4 Correct 35 ms 73064 KB Output is correct
5 Correct 38 ms 73156 KB Output is correct
6 Correct 35 ms 73216 KB Output is correct
7 Correct 36 ms 73172 KB Output is correct
8 Correct 36 ms 73080 KB Output is correct
9 Correct 35 ms 73104 KB Output is correct
10 Correct 36 ms 73188 KB Output is correct
11 Correct 36 ms 73028 KB Output is correct
12 Correct 35 ms 73088 KB Output is correct
13 Correct 36 ms 73080 KB Output is correct
14 Correct 35 ms 73116 KB Output is correct
15 Correct 35 ms 73032 KB Output is correct
16 Correct 36 ms 73044 KB Output is correct
17 Correct 35 ms 73188 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 73076 KB Output is correct
2 Correct 34 ms 72996 KB Output is correct
3 Correct 976 ms 240060 KB Output is correct
4 Correct 1225 ms 258432 KB Output is correct
5 Correct 903 ms 235096 KB Output is correct
6 Correct 812 ms 217120 KB Output is correct
7 Correct 904 ms 235332 KB Output is correct
8 Correct 1296 ms 288412 KB Output is correct
9 Correct 976 ms 231564 KB Output is correct
10 Correct 1695 ms 328120 KB Output is correct
11 Correct 587 ms 165880 KB Output is correct
12 Correct 497 ms 144100 KB Output is correct
13 Correct 1459 ms 296452 KB Output is correct
14 Correct 460 ms 141648 KB Output is correct
15 Correct 515 ms 143992 KB Output is correct
16 Correct 497 ms 143864 KB Output is correct
17 Correct 450 ms 141376 KB Output is correct
18 Correct 412 ms 150456 KB Output is correct
19 Correct 46 ms 76516 KB Output is correct
20 Correct 154 ms 108360 KB Output is correct
21 Correct 409 ms 137292 KB Output is correct
22 Correct 434 ms 144104 KB Output is correct
23 Correct 629 ms 157280 KB Output is correct
24 Correct 461 ms 143144 KB Output is correct
25 Correct 452 ms 140456 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 90676 KB Output is correct
2 Runtime error 2584 ms 1017976 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 90676 KB Output is correct
2 Runtime error 2584 ms 1017976 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 73044 KB Output is correct
2 Correct 35 ms 73032 KB Output is correct
3 Correct 35 ms 73044 KB Output is correct
4 Correct 35 ms 73064 KB Output is correct
5 Correct 38 ms 73156 KB Output is correct
6 Correct 35 ms 73216 KB Output is correct
7 Correct 36 ms 73172 KB Output is correct
8 Correct 36 ms 73080 KB Output is correct
9 Correct 35 ms 73104 KB Output is correct
10 Correct 36 ms 73188 KB Output is correct
11 Correct 36 ms 73028 KB Output is correct
12 Correct 35 ms 73088 KB Output is correct
13 Correct 36 ms 73080 KB Output is correct
14 Correct 35 ms 73116 KB Output is correct
15 Correct 35 ms 73032 KB Output is correct
16 Correct 36 ms 73044 KB Output is correct
17 Correct 35 ms 73188 KB Output is correct
18 Correct 35 ms 73076 KB Output is correct
19 Correct 34 ms 72996 KB Output is correct
20 Correct 976 ms 240060 KB Output is correct
21 Correct 1225 ms 258432 KB Output is correct
22 Correct 903 ms 235096 KB Output is correct
23 Correct 812 ms 217120 KB Output is correct
24 Correct 904 ms 235332 KB Output is correct
25 Correct 1296 ms 288412 KB Output is correct
26 Correct 976 ms 231564 KB Output is correct
27 Correct 1695 ms 328120 KB Output is correct
28 Correct 587 ms 165880 KB Output is correct
29 Correct 497 ms 144100 KB Output is correct
30 Correct 1459 ms 296452 KB Output is correct
31 Correct 460 ms 141648 KB Output is correct
32 Correct 515 ms 143992 KB Output is correct
33 Correct 497 ms 143864 KB Output is correct
34 Correct 450 ms 141376 KB Output is correct
35 Correct 412 ms 150456 KB Output is correct
36 Correct 46 ms 76516 KB Output is correct
37 Correct 154 ms 108360 KB Output is correct
38 Correct 409 ms 137292 KB Output is correct
39 Correct 434 ms 144104 KB Output is correct
40 Correct 629 ms 157280 KB Output is correct
41 Correct 461 ms 143144 KB Output is correct
42 Correct 452 ms 140456 KB Output is correct
43 Correct 132 ms 90676 KB Output is correct
44 Runtime error 2584 ms 1017976 KB Execution killed with signal 6
45 Halted 0 ms 0 KB -