| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 620735 |
2022-08-03T08:38:48 Z |
장태환(#8519) |
Railway Trip (JOI17_railway_trip) |
C++17 |
|
245 ms |
45364 KB |
#include <bits/stdc++.h>
using namespace std;
int depth[100100];
pair<int,int>glca[100100][20];
pair<int, int>pos[100100];
vector<int>li[100100];
vector<vector<pair<int, int>>>cst[100100];
vector<int>ll[100100], rr[100100];
int N,treeN;
int arr[100100];
struct tree
{
pair<int, int>stree[1 << 18];
void upd(int p, pair<int,int>t)
{
p += treeN;
stree[p] = t;
while (p > 1)
{
p /= 2;
stree[p] = max(stree[p * 2], stree[p * 2 + 1]);
}
}
pair<int,int> ge(int qs, int qe, int s = 0, int e = treeN - 1, int i = 1)
{
if (qs > e || s > qe)
return { 0,0 };
if (qs <= s && e <= qe)
return stree[i];
return max(ge(qs, qe, s, (s + e) / 2, i * 2), ge(qs, qe, (s + e) / 2 + 1, e, i * 2 + 1));
}
}lp,rp;
int c = 0;
void bu(pair<int,int>p,int s=0, int e=N-1,int d=0)
{
if (s > e)
return;
c++;
glca[c][0] = p;
depth[c] = d;
int i;
for (i = 0; i < 19; i++)
{
glca[c][i + 1] = glca[glca[c][i].first][i];
}
int rt = -lp.ge(s, e).second;
deque<int>r;
r.push_back(rt);
int cur = rt;
while (cur<e)
{
cur = -lp.ge(cur + 1, e).second;
r.push_back(cur);
}
cur = rt;
while (cur > s)
{
cur = rp.ge(s,cur-1).second;
r.push_front(cur);
}
ll[c].push_back(0);
for (i = 0; i < r.size(); i++)
{
if (i)
{
if (arr[r[i]] > arr[r[i - 1]])
{
ll[c].push_back(i);
}
if (arr[r[i]] < arr[r[i - 1]])
{
rr[c].push_back(i-1);
}
}
li[c].push_back(r[i]);
pos[r[i]] = { c,i };
vector<pair<int, int>>r;
int j;
for (j = 0; j < 20; j++)
{
r.push_back({ 0,0 });
}
cst[c].push_back(r);
}
rr[c].push_back(r.size() - 1);
for (i = 0; i < r.size(); i++)
{
int lv = N, rv = N;
int lc = lower_bound(ll[c].begin(), ll[c].end(), i) - ll[c].begin();
if (lc)
{
lv = min(lv, i - ll[c][lc - 1]+1);
}
if (lc != ll[c].size())
{
lv = min(lv, -i + ll[c][lc] + 1);
}
int rc = lower_bound(rr[c].begin(), rr[c].end(), i) - rr[c].begin();
if (rc)
{
rv = min(rv, i - rr[c][rc - 1] + 1);
}
if (rc != rr[c].size())
{
rv = min(rv, -i + rr[c][rc] + 1);
}
cst[c][i][0] = { lv,rv };
int j;
for (j = 0; j < 19; j++)
{
cst[c][i][j + 1] = { min(cst[c][i][j].first + cst[glca[c][j].first][glca[c][j].second][j].first,cst[c][i][j].second + cst[glca[c][j].first][glca[c][j].second+1][j].first), min(cst[c][i][j].first + cst[glca[c][j].first][glca[c][j].second][j].second,cst[c][i][j].second + cst[glca[c][j].first][glca[c][j].second + 1][j].second) };
}
}
int oc = c;
for (i = 1; i < r.size(); i++)
{
bu({ oc,i - 1 }, r[i - 1] + 1, r[i] - 1,d+1);
}
}
int lca(int a, int b)
{
if (depth[a] > depth[b])
swap(a, b);
int dd = depth[b] - depth[a];
int i;
for (i = 19; i >= 0; i--)
{
if (dd & (1 << i))
{
b = glca[b][i].first;
}
}
if (a == b)
return a;
for (i = 19; i >= 0; i--)
{
if (glca[a][i] != glca[b][i])
{
a = glca[a][i].first;
b = glca[b][i].first;
}
}
return glca[a][0].first;
}
pair<pair<int, int>, pair<int, int>>infs(pair<int, int>r, int dd)
{
pair<int, int>ct = { 0,0 };
int c = 0;
int i;
for (i = 19; i >= 0; i--)
{
if (dd & (1 << i))
{
pair<int, int>ncst;
if (c)
{
ncst.first = min(ct.first + cst[r.first][r.second][i].first, ct.second + cst[r.first][r.second + 1][i].first);
ncst.second = min(ct.first + cst[r.first][r.second][i].second, ct.second + cst[r.first][r.second + 1][i].second);
}
else
{
ncst.first = ct.first + cst[r.first][r.second][i].first;
ncst.second = ct.first + cst[r.first][r.second][i].second;
}
ct = ncst;
r = glca[r.first][i];
c = 1;
}
}
return{ r,ct };
}
int main()
{
int K, Q;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K >> Q;
for (treeN = 1; treeN <= N; treeN *= 2);
int i;
for (i = 0; i < N; i++)
{
cin >> arr[i];
lp.upd(i, { arr[i],-i });
rp.upd(i, { arr[i],i });
}
vector<pair<int, int>>r;
int j;
for (j = 0; j < 20; j++)
{
r.push_back({ 0,0 });
}
cst[0].push_back(r);
cst[0].push_back(r);
bu({ 0,0 });
while (Q--)
{
int a, b;
cin >> a >> b;
a--;
b--;
pair<int, int>xp = pos[a];
pair<int, int>yp = pos[b];
int lc = lca(xp.first, yp.first);
auto ld = infs(xp, depth[xp.first] - depth[lc]);
auto rd = infs(yp, depth[yp.first] - depth[lc]);
int ans = N;
ans = min(ans, ld.second.first + rd.second.first + abs(ld.first.second - rd.first.second));
if(depth[yp.first] - depth[lc])
ans = min(ans, ld.second.first + rd.second.second+ abs(ld.first.second - rd.first.second-1));
if(depth[xp.first] - depth[lc])
ans = min(ans, ld.second.second + rd.second.first + abs(ld.first.second - rd.first.second+1));
if (depth[yp.first] - depth[lc]&& depth[xp.first] - depth[lc])
ans = min(ans, ld.second.second + rd.second.second + abs(ld.first.second - rd.first.second));
if (lc != 1)
{
ld = infs(xp, depth[xp.first] - depth[lc]+1);
rd = infs(yp, depth[yp.first] - depth[lc]+1);
ans = min(ans, ld.second.first + rd.second.first + abs(ld.first.second - rd.first.second));
ans = min(ans, ld.second.first + rd.second.second + abs(ld.first.second - rd.first.second - 1));
ans = min(ans, ld.second.second + rd.second.first + abs(ld.first.second - rd.first.second + 1));
ans = min(ans, ld.second.second + rd.second.second + abs(ld.first.second - rd.first.second));
}
cout << ans - 1 << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
245 ms |
44728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
245 ms |
45364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
