Submission #803084

#	Time	Username	Problem	Language	Result	Execution time	Memory
803084		APROHACK	Sky Walking (IOI19_walk)	C++17	24 / 100	2584 ms	1017976 KiB

walk

#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 (stderr)

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43