| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 448086 |
2021-07-28T19:09:58 Z |
blue |
Sky Walking (IOI19_walk) |
C++17 |
|
4000 ms |
35148 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];
}
bool skywalk_leq(int p, int q)
{
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;
}
int min_skywalk(int p, int q)
{
if(p == no_skywalk) return q;
else if(q == no_skywalk) return p;
return p + q - max_skywalk(p, q);
}
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 deeper_walk;
if(l == r) deeper_walk = no_skywalk;
else deeper_walk = max_skywalk(left->locate_lower(I, J), right->locate_lower(I, J));
return max_skywalk(curr_walk, deeper_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_leq(w[ind + (1 << bit)], J)) continue;
ind += (1 << bit);
}
ind++;
int curr_walk = (ind >= w.size() ? no_skywalk : w[ind]);
int deeper_walk;
if(l == r) deeper_walk = no_skywalk;
else deeper_walk = min_skywalk(left->locate_higher(I, J), right->locate_higher(I, J));
return min_skywalk(curr_walk, deeper_walk);
}
}
};
vector<int> edge[maxM + 3];
vector<long long> dist[maxM + 3];
void add_edge(int u, int v, long long w)
{
cerr << "add edge " << u << ' ' << v << ' ' << w << '\n';
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++)
{
cerr << "j = " << j << ' ' << L[j] << ' ' << R[j] << '\n';
int top_walk = ST.locate_higher(R[j], j);
if(top_walk != no_skywalk)
{
cerr << "t1\n";
add_edge(j, top_walk, X[ R[top_walk] ] - X[ R[j] ] + Y[top_walk] - Y[j]);
}
int bottom_walk = ST.locate_lower(R[j], j);
// cerr << "locate lower " << R[j] << ' ' << j << ' ' << r_w << '\n';
if(bottom_walk != no_skywalk)
{
// cerr << "t2\n";
add_edge(j, bottom_walk, X[ R[bottom_walk] ] - X[ R[j] ] + Y[j] - Y[bottom_walk]);
}
if(L[j] == 0)
{
add_edge(S, j, X[ R[j] ] - X[0] + Y[j]);
cerr << "S " << j << ' ' << R[j] << ' ' << X[R[j]] << ' ' << X[0] << ' ' << Y[j] << '\n';
}
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';
// for(int j = 0; j < M; j++) cerr << "dist " << j << " = " << distS[j] << '\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:123:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | if(ind + (1 << bit) >= w.size()) continue;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
walk.cpp: In member function 'int segtree::locate_higher(int, int)':
walk.cpp:149:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | if(ind + (1 << bit) >= w.size()) continue;
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
walk.cpp:155:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | int curr_walk = (ind >= w.size() ? no_skywalk : w[ind]);
| ~~~~^~~~~~~~~~~
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:253:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
253 | 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 |
3 ms |
5708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1705 ms |
18732 KB |
Output is correct |
| 2 |
Correct |
3973 ms |
31632 KB |
Output is correct |
| 3 |
Execution timed out |
4085 ms |
35148 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1705 ms |
18732 KB |
Output is correct |
| 2 |
Correct |
3973 ms |
31632 KB |
Output is correct |
| 3 |
Execution timed out |
4085 ms |
35148 KB |
Time limit exceeded |
| 4 |
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 |
- |
