| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1067644 |
2024-08-20T22:28:08 Z |
jerzyk |
Sky Walking (IOI19_walk) |
C++17 |
|
192 ms |
110764 KB |
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
const int NN = 1<<20;
int tab[NN], hei[NN];
int drz[2 * N], drz2[2 * N];
int cnt = 0;
pair<int, int> co[NN];
vector<pair<int, ll>> ed[NN];
ll dis[NN];
pair<pair<int, int>, int> wal[NN];
bool vis[NN];
vector<int> poi[NN];
vector<int> sky[NN];
void DoDrz(int n)
{
for(int i = 1; i <= n; ++i)
drz[i + N] = hei[i];
for(int i = 1; i <= n; ++i)
drz2[i + N] = 1;
for(int i = N - 1; i >= 1; --i)
drz[i] = max(drz[i * 2], drz[i * 2 + 1]);
for(int i = N - 1; i >= 1; --i)
drz2[i] = drz2[i * 2] + drz2[i * 2 + 1];
}
int Find(int a, int b, int x, int r)
{
a += N - 1; b += N + 1;
int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
while(a / 2 != b / 2)
{
if(a % 2 == 0 && drz[a + 1] >= x)
{
if(a1 == 0)
a1 = a + 1;
a2 = a + 1;
}
if(b % 2 == 1 && drz[b - 1] >= x)
{
if(b1 == 0)
b1 = b - 1;
b2 = b - 1;
}
a /= 2; b /= 2;
}
if(r == 0)
a = a1;
if(a == 0)
a = b2;
if(r == 1)
a = b1;
if(a == 0)
a = a2;
while(a < N)
{
a = a * 2 + r;
if(drz[a] < x) a ^= 1;
}
return a - N;
}
bool C(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
return (make_pair(a.nd, a.st) < make_pair(b.nd, b.st));
}
void Clr(int v, int a, int b, int pz, int kz, int id)
{
if(drz2[v] <= 0 || a > kz || b < pz) return;
if(v > N)
{
v -= N;
//cerr << "clr: " << v << " " << id << "\n";
if(hei[v] >= wal[id].nd)
sky[v].pb(id);
--drz2[v + N];
return;
}
Clr(v * 2, a, (a + b) / 2, pz, kz, id);
Clr(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz, id);
drz2[v] = drz2[v * 2] + drz2[v * 2 + 1];
}
inline ll D(int i, int j)
{
ll d1 = max(co[i].st - co[j].st, co[j].st - co[i].st);
ll d2 = max(co[i].nd - co[j].nd, co[j].nd - co[i].nd);
return d1 + d2;
}
inline void A(int x, int y)
{
ll d = D(x, y);
ed[x].pb(make_pair(y, d)); ed[y].pb(make_pair(x, d));
}
void SanInput(int n, int &k, int u, int v)
{
int dod = 0;
sort(wal + 1, wal + 1 + k, C);
for(int i = 1; i <= k; ++i)
{
//cerr << "skypath: " << i << " " << wal[i].st.st - 1 << " " << wal[i].st.nd - 1 << " " << wal[i].nd << "\n";
vector<int> cur = {wal[i].st.st, wal[i].st.nd}, hl;
if(wal[i].st.st < u && wal[i].st.nd > u)
{
int v1 = Find(1, u, wal[i].nd, 1), v2 = Find(u, n, wal[i].nd, 0);
cur.pb(v1); cur.pb(v2);
}
if(wal[i].st.st < v && wal[i].st.nd > v)
{
int v1 = Find(1, v, wal[i].nd, 1), v2 = Find(v, n, wal[i].nd, 0);
cur.pb(v1); cur.pb(v2);
}
sort(cur.begin(), cur.end());
for(int j = 0; j < (int)cur.size(); ++j)
if(j == 0 || cur[j] != cur[j - 1]) hl.pb(cur[j]);
cur = hl;
wal[i].st.nd = cur[1];
Clr(1, 0, N - 1, wal[i].st.st, wal[i].st.nd, i);
sky[cur[0]].pb(i);
sky[cur[1]].pb(i);
for(int j = 1; j < (int)cur.size() - 1; ++j)
{
++dod;
wal[k + dod] = make_pair(make_pair(cur[j], cur[j + 1]), wal[i].nd);
Clr(1, 0, N - 1, wal[k + dod].st.st, wal[k + dod].st.nd, i);
sky[cur[j]].pb(k + dod);
sky[cur[j + 1]].pb(k + dod);
}
//for(int j = 1; j < (int)cur.size() - 1; ++j)
//{
//cerr << cur[j] - 1 << " ";
//}
//cerr << "\n";
}
k += dod;
cnt = n;
for(int i = 1; i <= n; ++i)
{
vector<int> hlp;
for(int j = 0; j < (int)sky[i].size(); ++j)
if(j == 0 || sky[i][j] != sky[i][j - 1]) hlp.pb(sky[i][j]);
sky[i] = hlp;
co[i] = make_pair(tab[i], 0);
int pr = i;
//cerr << "Sky: " << i << " " << "\n";
for(int j = 0; j < (int)sky[i].size(); ++j)
{
if(j != 0) pr = cnt;
if(j == 0 || wal[sky[i][j]].nd != wal[sky[i][j - 1]].nd)
{++cnt; co[cnt] = make_pair(tab[i], wal[sky[i][j]].nd); A(cnt, pr);}
poi[sky[i][j]].pb(cnt);
//cerr << sky[i][j] << " ";
}
//cerr << "\n";
}
for(int i = 1; i <= k; ++i)
for(int j = 1; j < (int)poi[i].size(); ++j)
A(poi[i][j - 1], poi[i][j]);
}
void Dijkstra(int s)
{
int n = cnt;
priority_queue<pair<ll, int>> q;
for(int i = 1; i <= n; ++i) dis[i] = I;
dis[s] = 0LL;
q.push(make_pair(0LL, s));
while((int)q.size() > 0)
{
int v = q.top().nd; q.pop();
if(vis[v]) continue;
vis[v] = true;
//cerr << "Dijkstra: " << v << " " << co[v].st << " " << co[v].nd << " " << dis[v] << "\n";
for(int i = 0; i < (int)ed[v].size(); ++i)
{
//cout << "ed: " << ed[v][i].st << " " << ed[v][i].nd << "\n";
ll d = dis[v] + ed[v][i].nd;
if(d < dis[ed[v][i].st])
{
dis[ed[v][i].st] = d;
q.push(make_pair(-d, ed[v][i].st));
}
}
}
}
long long min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g)
{
int u = _s + 1, v = _g + 1;
int n = _x.size(), k = _l.size();
for(int i = 1; i <= n; ++i)
{tab[i] = _x[i - 1]; hei[i] = _h[i - 1]; ++cnt;}
for(int i = 1; i <= k; ++i)
wal[i] = make_pair(make_pair(_l[i - 1] + 1, _r[i - 1] + 1), _y[i - 1]);
DoDrz(n);
SanInput(n, k, u, v);
Dijkstra(u);
if(dis[v] == I) return -1;
return dis[v];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
76372 KB |
Output is correct |
| 2 |
Correct |
35 ms |
76380 KB |
Output is correct |
| 3 |
Correct |
34 ms |
76368 KB |
Output is correct |
| 4 |
Correct |
32 ms |
76248 KB |
Output is correct |
| 5 |
Correct |
32 ms |
76372 KB |
Output is correct |
| 6 |
Incorrect |
33 ms |
76376 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
76380 KB |
Output is correct |
| 2 |
Correct |
33 ms |
76236 KB |
Output is correct |
| 3 |
Incorrect |
192 ms |
110764 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
88060 KB |
Output is correct |
| 2 |
Incorrect |
173 ms |
109140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
88060 KB |
Output is correct |
| 2 |
Incorrect |
173 ms |
109140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
76372 KB |
Output is correct |
| 2 |
Correct |
35 ms |
76380 KB |
Output is correct |
| 3 |
Correct |
34 ms |
76368 KB |
Output is correct |
| 4 |
Correct |
32 ms |
76248 KB |
Output is correct |
| 5 |
Correct |
32 ms |
76372 KB |
Output is correct |
| 6 |
Incorrect |
33 ms |
76376 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
