| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 452034 |
2021-08-03T16:23:22 Z |
blue |
Sky Walking (IOI19_walk) |
C++17 |
|
1241 ms |
105612 KB |
#include "walk.h"
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
int N;
vector<int> X;
vector<int> H;
int M;
vector<int> L;
vector<int> R;
vector<int> Y;
int S;
int G;
const int INF = 1e9 + 1;
const int MX = 100'000;
const long long LONG_INF = 1'000'000'000'000'000'0LL;
int higher_skywalk(int w1, int w2)
{
if(w1 == -1) return w2;
else if(w2 == -1) return w1;
else if(Y[w1] == Y[w2]) return max(w1, w2);
else if(Y[w1] > Y[w2]) return w1;
else return w2;
}
struct point
{
int b; //building
int s; //skywalk
int i;
point()
{
;
}
point(int B, int S)
{
b = B;
s = S;
}
point(int B, int S, int I)
{
b = B;
s = S;
i = I;
}
};
bool operator < (point A, point B)
{
if(A.b == B.b) return A.s < B.s;
return A.b < B.b;
}
set<point> points;
struct walk_segtree
{
int l;
int r;
vector<int> w;
walk_segtree* left = NULL;
walk_segtree* right = NULL;
walk_segtree()
{
;
}
walk_segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new walk_segtree(l, m);
right = new walk_segtree(m+1, r);
}
void add_skywalk(int W)
{
if(R[W] < l || r < L[W]) return;
else if(L[W] <= l && r <= R[W])
{
w.push_back(W);
}
else
{
left->add_skywalk(W);
right->add_skywalk(W);
}
}
void sort_skywalks()
{
sort(w.begin(), w.end(), [] (int u, int v)
{
return Y[u] < Y[v];
});
if(left != NULL)
{
left->sort_skywalks();
right->sort_skywalks();
}
}
int locate_lower(int I, int W)
{
if(r < I || I < l) return -1;
int ind = -1;
for(int bit = 20; bit >= 0; bit--)
{
if(ind + (1 << bit) >= w.size()) continue;
if(higher_skywalk(w[ind + (1 << bit)], W) == w[ind + (1 << bit)]) continue;
ind += (1 << bit);
}
int curr_best = (ind == -1 ? -1 : w[ind]);
if(left != NULL)
{
curr_best = higher_skywalk(curr_best, left->locate_lower(I, W));
curr_best = higher_skywalk(curr_best, right->locate_lower(I, W));
}
return curr_best;
}
};
int taller_building(int b1, int b2)
{
if(b1 == -1) return b2;
else if(b2 == -1) return b1;
else if(H[b1] > H[b2]) return b1;
else return b2;
}
struct build_segtree
{
int l;
int r;
int h; //maximum height of a building
build_segtree* left = NULL;
build_segtree* right = NULL;
build_segtree()
{
;
}
build_segtree(int L, int R)
{
l = L;
r = R;
if(l == r) h = H[L];
else
{
int m = (l+r)/2;
left = new build_segtree(l, m);
right = new build_segtree(m+1, r);
h = max(left->h, right->h);
}
}
int rangemax(int L, int R)
{
if(R < L) return -INF;
else if(R < l || r < L) return -INF;
else if(L <= l && r <= R) return h;
else return max(left->rangemax(L, R), right->rangemax(L, R));
}
};
vector<int>* edge;
vector<long long>* dist;
vector<long long> src_dist(100+MX, LONG_INF);
void add_edge(int u, int v, long long w)
{
edge[u].push_back(v);
dist[u].push_back(w);
edge[v].push_back(u);
dist[v].push_back(w);
// cerr << u << ' ' << v << ' ' << w << '\n';
// assert(w >= 0);
}
struct pos
{
int i;
};
bool operator < (pos A, pos B)
{
if(src_dist[A.i] == src_dist[B.i]) return A.i < B.i;
return src_dist[A.i] < src_dist[B.i];
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
// cerr << "A\n";
N = x.size();
X = x;
H = h;
M = l.size();
L = l;
R = r;
Y = y;
S = s;
G = g;
walk_segtree S_W(0, N-1);
for(int j = 0; j < M; j++)
S_W.add_skywalk(j);
S_W.sort_skywalks();
// cerr << "B\n";
for(int j = 0; j < M; j++)
{
int LL = S_W.locate_lower(L[j], j);
if(LL != -1)
points.insert(point(L[j], LL));
int RL = S_W.locate_lower(R[j], j);
if(RL != -1)
points.insert(point(R[j], RL));
}
// cerr << "C\n";
for(int j = 0; j < M; j++)
{
if(L[j] <= S && S <= R[j] && Y[j] <= H[S])
{
points.insert(point(S, j));
}
if(L[j] <= G && G <= R[j] && Y[j] <= H[G])
points.insert(point(G, j));
}
// cerr << "D\n";
build_segtree S_B(0, N-1);
// cerr << "E\n";
int S_skywalk = M;
L.push_back(S);
R.push_back(S);
Y.push_back(0);
int G_skywalk = M+1;
L.push_back(G);
R.push_back(G);
Y.push_back(0);
// cerr << "F\n";
for(int j = 0; j < M; j++)
{
// cerr << "j = " << j << '\n';
for(int PT: vector<int>{S, G})
{
// S_B.rangemax(L[j], min(R[j], PT));
// cerr << "query done\n";
if(L[j] <= PT && S_B.rangemax(L[j], min(R[j], PT)) >= Y[j])
{
// cerr << "entered if statement\n";
int lo = L[j];
int hi = min(R[j], PT);
int mid;
// cerr << "check\n";
while(lo != hi)
{
mid = (lo+hi)/2 + 1;
// cerr << lo << ' ' << hi << ' ' << mid << '\n';
if(S_B.rangemax(mid, hi) >= Y[j])
lo = mid;
else
hi = mid-1;
}
// cerr << lo << ' ' << hi << '\n';
mid = lo;
if(H[mid] >= Y[j])
{
int tmp = S_W.locate_lower(mid, j);
if(tmp != -1)
{
points.insert(point(mid, j));
points.insert(point(mid, tmp));
}
}
}
// else cerr << "not entered\n";
// cerr << "left done\n";
if(PT <= R[j] && S_B.rangemax(max(L[j], PT), R[j]) >= Y[j])
{
int lo = max(L[j], PT);
int hi = R[j];
int mid;
while(lo != hi)
{
mid = (lo+hi)/2;
if(S_B.rangemax(lo, mid) >= Y[j])
hi = mid;
else
lo = mid+1;
}
mid = lo;
if(H[mid] >= Y[j])
{
int tmp = S_W.locate_lower(mid, j);
if(tmp != -1)
{
points.insert(point(mid, j));
points.insert(point(mid, tmp));
}
}
}
}
}
// cerr << "G\n";
int P = points.size();
vector<point> points_vector;
int ct = 0;
while(!points.empty())
{
point pt = *points.begin();
points.erase(points.begin());
ct++;
pt.i = ct-1;
points_vector.push_back(pt);
}
// cerr << "H\n";
ct++;
points_vector.push_back(point(S, S_skywalk, ct-1));
int S_vertex = ct-1;
ct++;
points_vector.push_back(point(G, G_skywalk, ct-1));
int G_vertex = ct-1;
// for(point pt: points_vector) cerr << X[pt.b] << ' ' << Y[pt.s] << '\n';
// cerr << "check\n";
// cerr << "I\n";
edge = new vector<int>[ct];
dist = new vector<long long>[ct];
sort(points_vector.begin(), points_vector.end(), [] (point p1, point p2)
{
if(p1.b == p2.b) return (higher_skywalk(p1.s, p2.s) == p2.s);
return p1.b < p2.b;
});
for(int z = 0; z+1 < points_vector.size(); z++)
{
point p1 = points_vector[z];
point p2 = points_vector[z+1];
if(p1.b == p2.b)
{
add_edge(p1.i, p2.i, Y[p2.s] - Y[p1.s]);
// cerr << "adding edge from " << X[p1.b] << ' ' << Y[p1.s] << " to " << X[p2.b] << ' ' << Y[p2.s] << " with weight " << Y[p2.s] - Y[p1.s] << '\n';
}
}
sort(points_vector.begin(), points_vector.end(), [] (point p1, point p2)
{
if(p1.s == p2.s) return p1.b < p2.b;
return higher_skywalk(p1.s, p2.s) == p2.s;
});
for(int z = 0; z+1 < points_vector.size(); z++)
{
point p1 = points_vector[z];
point p2 = points_vector[z+1];
if(p1.s == p2.s)
{
add_edge(p1.i, p2.i, X[p2.b] - X[p1.b]);
// cerr << "adding edge from " << X[p1.b] << ' ' << Y[p1.s] << " to " << X[p2.b] << ' ' << Y[p2.s] << " with weight " << X[p2.b] - X[p1.b] << '\n';
}
}
// cerr << "Q\n";
src_dist[S_vertex] = 0;
set<pos> tbv;
for(int i = 0; i < ct; i++) tbv.insert(pos{i});
while(!tbv.empty())
{
int u = tbv.begin()->i;
tbv.erase(tbv.begin());
// cerr << "u = " << u << '\n';
// cerr << src_dist[u] << '\n';
for(int e = 0; e < edge[u].size(); e++)
{
int v = edge[u][e];
long long w = dist[u][e];
if(src_dist[v] > src_dist[u] + w)
{
tbv.erase(pos{v});
src_dist[v] = src_dist[u] + w;
// cerr << "w = " << w << '\n';
tbv.insert(pos{v});
}
}
}
// cerr << "Z\n";
long long ans = src_dist[G_vertex];
if(ans >= LONG_INF)
ans = -1;
return ans;
}
Compilation message
walk.cpp: In member function 'int walk_segtree::locate_lower(int, int)':
walk.cpp:126:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | if(ind + (1 << bit) >= w.size()) continue;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
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:412:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
412 | for(int z = 0; z+1 < points_vector.size(); z++)
| ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:434:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
434 | for(int z = 0; z+1 < points_vector.size(); z++)
| ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:458:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
458 | for(int e = 0; e < edge[u].size(); e++)
| ~~^~~~~~~~~~~~~~~~
walk.cpp:374:6: warning: unused variable 'P' [-Wunused-variable]
374 | int P = points.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Correct |
1 ms |
972 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1088 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Correct |
1 ms |
972 KB |
Output is correct |
| 3 |
Runtime error |
1241 ms |
105612 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
399 ms |
45004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
399 ms |
45004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
972 KB |
Output is correct |
| 2 |
Correct |
1 ms |
972 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1088 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 18 |
Correct |
1 ms |
972 KB |
Output is correct |
| 19 |
Correct |
1 ms |
972 KB |
Output is correct |
| 20 |
Runtime error |
1241 ms |
105612 KB |
Execution killed with signal 11 |
| 21 |
Halted |
0 ms |
0 KB |
- |
