#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);
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:98: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]
98 | 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:132: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]
132 | for (ll j = 1 ; j < puntosEnB[i].size() ; j ++){
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
73036 KB |
Output is correct |
| 2 |
Correct |
35 ms |
73084 KB |
Output is correct |
| 3 |
Correct |
36 ms |
73036 KB |
Output is correct |
| 4 |
Correct |
36 ms |
73040 KB |
Output is correct |
| 5 |
Incorrect |
36 ms |
73212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
72980 KB |
Output is correct |
| 2 |
Correct |
35 ms |
73032 KB |
Output is correct |
| 3 |
Incorrect |
1004 ms |
239968 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
90852 KB |
Output is correct |
| 2 |
Runtime error |
2761 ms |
1017852 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
90852 KB |
Output is correct |
| 2 |
Runtime error |
2761 ms |
1017852 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
73036 KB |
Output is correct |
| 2 |
Correct |
35 ms |
73084 KB |
Output is correct |
| 3 |
Correct |
36 ms |
73036 KB |
Output is correct |
| 4 |
Correct |
36 ms |
73040 KB |
Output is correct |
| 5 |
Incorrect |
36 ms |
73212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
