| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 298084 |
2020-09-12T11:32:03 Z |
SamAnd |
Sky Walking (IOI19_walk) |
C++17 |
|
39 ms |
14720 KB |
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;
const ll INF = 1000000009000000009;
int n, m;
map<int, vector<int> > g[N];
set<pair<int, int> > c;
set<int> s[N];
pair<int, int> maxu[N * 4];
void ubd(int tl, int tr, int x, int y, int pos)
{
if (tl == tr)
{
maxu[pos] = m_p(y, x);
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, y, pos * 2);
else
ubd(m + 1, tr, x, y, pos * 2 + 1);
maxu[pos] = max(maxu[pos * 2], maxu[pos * 2 + 1]);
}
pair<int, int> qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return m_p(-1, -1);
if (tl == l && tr == r)
return maxu[pos];
int m = (tl + tr) / 2;
return max(qry(tl, m, l, min(m, r), pos * 2),
qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
struct ban
{
pair<int, int> u;
ll d;
ban(){}
ban(pair<int, int> u, ll d)
{
this->u = u;
this->d = d;
}
};
bool operator<(const ban& a, const ban& b)
{
return a.d > b.d;
}
map<int, vector<pair<int, int> > > mp;
vector<int> v[N];
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 F)
{
n = sz(x);
m = sz(y);
if (!(S == 0 && F == n - 1))
{
for (int i = 0; i < n; ++i)
ubd(0, n - 1, i, h[i], 1);
for (int i = 0; i < m; ++i)
{
vector<int> v;
while (1)
{
pair<int, int> u = qry(0, n - 1, l[i], r[i], 1);
if (u.fi < y[i])
break;
v.push_back(u.se);
ubd(0, n - 1, u.se, -1, 1);
}
sort(all(v));
for (int j = 0; j < sz(v); ++j)
{
s[v[j]].insert(y[i]);
ubd(0, n - 1, v[j], h[v[j]], 1);
}
for (int j = 0; j < sz(v) - 1; ++j)
{
g[v[j]][y[i]].push_back(v[j + 1]);
g[v[j + 1]][y[i]].push_back(v[j]);
}
}
s[S].insert(0);
s[F].insert(0);
priority_queue<ban> q;
q.push(ban(m_p(S, 0), 0));
while (1)
{
ban t;
do
{
if (q.empty())
return -1;
t = q.top();
q.pop();
} while (c.find(t.u) != c.end());
c.insert(t.u);
if (t.u == m_p(F, 0))
return t.d;
for (int i = 0; i < g[t.u.fi][t.u.se].size(); ++i)
{
ban h = ban(m_p(g[t.u.fi][t.u.se][i], t.u.se), t.d);
h.d += abs(x[t.u.fi] - x[h.u.fi]);
q.push(h);
}
auto it = s[t.u.fi].find(t.u.se);
if (it != (--s[t.u.fi].end()))
{
++it;
ban h = ban(m_p(t.u.fi, *it), t.d + *it - t.u.se);
q.push(h);
--it;
}
if (it != s[t.u.fi].begin())
{
--it;
ban h = ban(m_p(t.u.fi, *it), t.d + t.u.se - *it);
q.push(h);
++it;
}
}
}
for (int i = 0; i < m; ++i)
{
mp[y[i]].push_back(m_p(l[i], 1));
mp[y[i]].push_back(m_p(r[i] + 1, -1));
}
for (auto it = mp.begin(); it != mp.end(); ++it)
{
sort(all(it->se));
int q = 0;
int l = it->se[0].fi;
int r = l;
for (int i = 0; i < sz(it->se); ++i)
{
q += it->se[i].se;
if (q && it->se[i + 1].fi != it->se[i].fi)
{
r = it->se[i + 1].fi;
}
else
{
v[l].push_back(it->fi);
v[r].push_back(-it->fi);
}
}
}
return -1;
/*map<int, ll> dp;
set<int> s;
s.insert(0);
dp[0] = 0;
v[0].push_back(0);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < sz(v[i]); ++j)
{
int y = v[i][j];
if (y > 0)
{
auto it = s.upper_bound(y);
dp[y] = INF;
if (it != s.end())
dp[y] = min(dp[y], dp[*it] + abs(y - *it));
if (!s.empty() && it != s.begin())
{
--it;
dp[y] = min(dp[y], dp[*it] + abs(y - *it));
}
s.insert(y);
}
}
if (i == n - 1)
break;
for (int j = 0; j < sz(v[i]); ++j)
{
int y = v[i][j];
if (y <= 0)
{
y *= -1;
s.erase(y);
auto it = s.upper_bound(y);
if (it != s.end())
dp[*it] = min(dp[*it], dp[y] + abs(*it - y));
if (!s.empty() && it != s.begin())
{
--it;
dp[*it] = min(dp[*it], dp[y] + abs(*it - y));
}
}
}
}
ll ans = INF;
for (auto it = s.begin(); it != s.end(); ++it)
{
ans = min(ans, dp[*it] + x[n - 1] + *it);
}
if (ans == INF)
return -1;
return ans;*/
}
Compilation message
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:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int i = 0; i < g[t.u.fi][t.u.se].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
12032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
12032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
14720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
14720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
12032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
