| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 448050 |
2021-07-28T16:31:22 Z |
blue |
Sky Walking (IOI19_walk) |
C++17 |
|
210 ms |
15240 KB |
#include "walk.h"
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxN = 100'000;
const int maxM = 100'000;
const int lg = 19;
const long long INF = 1'000'000'000'000'000'000LL;
int N;
vector<int> X;
vector<int> H;
int M;
vector<int> L;
vector<int> R;
vector<int> Y;
const int S = maxM;
const int G = maxM + 1;
const int no_skywalk = -1;
bool skywalk_comp(int p, int q) //compare skywalks by height
{
if(p == no_skywalk) return 1; //-1 -> height = -INF
else if(q == no_skywalk) return 0;
else if(Y[p] == Y[q]) return p < q;
else return Y[p] < Y[q];
}
int max_skywalk(int p, int q)
{
if(skywalk_comp(p, q)) return q;
else return p;
}
struct segtree
{
int l;
int r;
vector<int> w; //skywalks sorted by height
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void add_skywalk(int i) //over L[i] to R[i];
{
if(R[i] < l || r < L[i]) return;
else if(L[i] <= l && r <= R[i])
{
w.push_back(i);
}
else
{
left->add_skywalk(i);
right->add_skywalk(i);
}
}
void sort_skywalks()
{
sort(w.begin(), w.end(), skywalk_comp);
if(l != r)
{
left->sort_skywalks();
right->sort_skywalks();
}
}
int locate_lower(int I, int J) //building i, skywalk j
{
//if(I < L[J] || R[J] < I) return -1; //guaranteed;
if(I < l || r < I) return no_skywalk;
else
{
int ind = -1;
for(int bit = lg; bit >= 0; bit--)
{
if(ind + (1 << bit) >= w.size()) continue;
if(!skywalk_comp(w[ind + (1 << bit)], J)) continue;
ind += (1 << bit);
}
if(ind != -1 && w[ind] == I) ind--;
int curr_walk = (ind == -1) ? no_skywalk : w[ind];
int lower_walk;
if(l == r) lower_walk = no_skywalk;
else lower_walk = max_skywalk(left->locate_lower(I, J), right->locate_lower(I, J));
return max_skywalk(curr_walk, lower_walk);
}
}
// int locate_higher(int I, int J) //building i, skywalk j
// {
// //if(I < L[J] || R[J] < I) return -1; //guaranteed;
// if(I < l || r < I) return no_skywalk;
// else
// {
// int ind = -1;
// for(int bit = lg; bit >= 0; bit--)
// {
// if(ind + (1 << bit) >= w.size()) continue;
// if(!skywalk_comp(w[ind + (1 << bit)], J)) continue;
// ind += (1 << bit);
// }
// }
// }
};
vector<int> edge[maxM + 3];
vector<long long> dist[maxM + 3];
void add_edge(int u, int v, long long w)
{
edge[u].push_back(v);
dist[u].push_back(w);
}
vector<long long> distS(maxM + 3, INF);
struct pos
{
int i;
};
bool operator < (pos A, pos B)
{
if(distS[A.i] == distS[B.i]) return A.i < B.i;
return distS[A.i] < distS[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)
{
N = x.size();
X = x;
H = h;
M = l.size();
L = l;
R = r;
Y = y;
//source = 0, destination = n-1
segtree ST(0, N-1);
for(int j = 0; j < M; j++)
ST.add_skywalk(j);
ST.sort_skywalks();
for(int j = 0; j < M; j++)
{
int l_w = ST.locate_lower(L[j], j);
if(l_w != no_skywalk)
{
add_edge(l_w, j, X[ R[j] ] - X[ L[j] ] + Y[j] - Y[l_w]);
}
int r_w = ST.locate_lower(R[j], j);
if(r_w != no_skywalk)
{
add_edge(j, r_w, X[ R[r_w] ] - X[ R[j] ] + Y[j] - Y[r_w]);
}
if(L[j] == 0)
add_edge(S, j, X[ R[j] ] + Y[j]);
if(R[j] == N-1)
add_edge(j, G, Y[j]);
}
distS[S] = 0;
set<pos> tbv;
for(int j = 0; j < M; j++) tbv.insert(pos{j});
tbv.insert(pos{S});
tbv.insert(pos{G});
while(!tbv.empty())
{
int u = tbv.begin()->i;
tbv.erase(tbv.begin());
for(int e = 0; e < edge[u].size(); e++)
{
int v = edge[u][e];
long long wt = dist[u][e];
if(distS[v] > distS[u] + wt)
{
tbv.erase(pos{v});
// cerr << u << ' ' << v << ' ' << distS[u] + wt << '\n';
distS[v] = distS[u] + wt;
tbv.insert(pos{v});
}
}
}
// for(int j = 0; j < M; j++) cerr << j << ' ' << distS[j] << '\n';
// cerr << "S " << distS[S] << '\n';
// cerr << "G " << distS[G] << '\n';
if(distS[G] == INF) distS[G] = -1;
return distS[G];
}
Compilation message
walk.cpp: In member function 'int segtree::locate_lower(int, int)':
walk.cpp:108:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | 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:221:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
221 | for(int e = 0; e < edge[u].size(); e++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
15240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
15240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
