# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
623176 |
2022-08-05T09:34:23 Z |
wiwiho |
Sky Walking (IOI19_walk) |
C++14 |
|
1162 ms |
100620 KB |
#include "walk.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
struct bridge{
int l, r, y;
int lid = -1, rid = -1;
};
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int from, int to){
int n = X.size();
int m = L.size();
if(from > to) swap(from, to);
vector<vector<int>> sp(m);
for(int i = 0; i < m; i++){
sp[i].eb(L[i]);
sp[i].eb(R[i]);
}
vector<vector<int>> lp(n + 1), rp(n + 1);
for(int i = 0; i < m; i++){
lp[L[i]].eb(i);
rp[R[i]].eb(i);
}
{
vector<int> v;
set<int> now;
for(int i = 0; i < n; i++){
while(!v.empty() && H[v.back()] <= H[i]) v.pob;
v.eb(i);
for(int j : lp[i]) now.insert(j);
if(i == from || i == to){
for(int j : now){
int y = Y[j];
auto it = lower_bound(iter(v), y, [&](int e, int val){ return val <= H[e]; } );
it--;
int pos = *it;
sp[j].eb(pos);
}
}
for(int j : rp[i]) now.erase(j);
}
}
{
vector<int> v;
set<int> now;
for(int i = n - 1; i >= 0; i--){
while(!v.empty() && H[v.back()] <= H[i]) v.pob;
v.eb(i);
for(int j : rp[i]) now.insert(j);
if(i == from || i == to){
for(int j : now){
int y = Y[j];
auto it = lower_bound(iter(v), y, [&](int e, int val){ return val <= H[e]; } );
it--;
int pos = *it;
sp[j].eb(pos);
}
}
for(int j : lp[i]) now.erase(j);
}
}
vector<bridge> bri;
for(int i = 0; i < m; i++){
lsort(sp[i]);
uni(sp[i]);
//cerr << "bridge " << i << " : ";
//printv(sp[i], cerr);
//assert(sp[i].front() == L[i]); OK
//assert(sp[i].back() == R[i]); OK
for(int j = 0; j + 1 < (int)sp[i].size(); j++){
bri.eb(bridge({sp[i][j], sp[i][j + 1], Y[i]}));
}
}
fill(iter(lp), vector<int>());
fill(iter(rp), vector<int>());
for(auto i : bri){
lp[i.l].eb(i.y);
rp[i.r].eb(i.y);
}
vector<pii> ps;
{
multiset<int> now;
for(int i = 0; i < n; i++){
for(int j : lp[i]) now.insert(j);
auto add = [&](int y){
//cerr << "add " << X[i] << " " << y << "\n";
ps.eb(mp(X[i], y));
auto it = now.upper_bound(y);
if(it != now.end() && *it <= H[i]) ps.eb(mp(X[i], *it));
it = now.lower_bound(y);
if(it != now.begin()) ps.eb(mp(X[i], *prev(it)));
};
for(int j : lp[i]) add(j);
for(int j : rp[i]) add(j);
for(int j : rp[i]) now.erase(now.find(j));
}
}
ps.eb(mp(X[from], 0));
ps.eb(mp(X[to], 0));
lsort(ps);
uni(ps);
//printv(ps, cerr);
auto getid = [&](int x, int y){
return lower_bound(iter(ps), mp(x, y)) - ps.begin();
};
int sid = getid(X[from], 0);
int gid = getid(X[to], 0);
for(auto& i : bri){
i.lid = getid(X[i.l], i.y);
i.rid = getid(X[i.r], i.y);
}
int sz = ps.size();
vector<vector<pll>> g(sz);
auto addedge = [&](int u, int v){
ll w = abs(ps[u].F - ps[v].F) + abs(ps[u].S - ps[v].S);
//cerr << "addedge " << u << " " << ps[u] << " " << v << " " << ps[v] << " " << w << "\n";
g[u].eb(mp(v, w));
g[v].eb(mp(u, w));
};
for(int i = 0; i + 1 < sz; i++){
if(ps[i].F == ps[i + 1].F){
addedge(i, i + 1);
}
}
vector<int> tmp(sz);
iota(iter(tmp), 0);
auto comp = [&](int a, int b){ return mp(ps[a].S, ps[a].F) < mp(ps[b].S, ps[b].F); };
sort(iter(tmp), comp);
for(auto i : bri){
int pos = lower_bound(iter(tmp), i.lid, comp) - tmp.begin();
while(tmp[pos] != i.rid){
int now = tmp[pos], nxt = tmp[pos + 1];
assert(X[i.l] <= ps[now].F && ps[now].F <= X[i.r] && ps[now].S == i.y);
assert(X[i.l] <= ps[nxt].F && ps[nxt].F <= X[i.r] && ps[nxt].S == i.y);
addedge(now, nxt);
pos++;
}
}
vector<ll> dis(sz, 1LL << 60);
std::priority_queue<pll, vector<pll>, greater<>> pq;
pq.push(mp(0, sid));
dis[sid] = 0;
while(!pq.empty()){
int now = pq.top().S;
ll d = pq.top().F;
pq.pop();
if(d != dis[now]) continue;
for(pll i : g[now]){
if(dis[i.F] <= d + i.S) continue;
dis[i.F] = d + i.S;
pq.push(mp(d + i.S, i.F));
}
}
return dis[gid];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
679 ms |
69112 KB |
Output is correct |
4 |
Correct |
649 ms |
76088 KB |
Output is correct |
5 |
Correct |
440 ms |
58948 KB |
Output is correct |
6 |
Correct |
426 ms |
54424 KB |
Output is correct |
7 |
Incorrect |
427 ms |
59088 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
15800 KB |
Output is correct |
2 |
Correct |
898 ms |
87972 KB |
Output is correct |
3 |
Correct |
944 ms |
91836 KB |
Output is correct |
4 |
Correct |
1051 ms |
99324 KB |
Output is correct |
5 |
Correct |
1162 ms |
100620 KB |
Output is correct |
6 |
Correct |
1087 ms |
94136 KB |
Output is correct |
7 |
Correct |
430 ms |
54168 KB |
Output is correct |
8 |
Correct |
363 ms |
43052 KB |
Output is correct |
9 |
Correct |
985 ms |
88884 KB |
Output is correct |
10 |
Correct |
450 ms |
57176 KB |
Output is correct |
11 |
Incorrect |
11 ms |
3452 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
15800 KB |
Output is correct |
2 |
Correct |
898 ms |
87972 KB |
Output is correct |
3 |
Correct |
944 ms |
91836 KB |
Output is correct |
4 |
Correct |
1051 ms |
99324 KB |
Output is correct |
5 |
Correct |
1162 ms |
100620 KB |
Output is correct |
6 |
Correct |
1087 ms |
94136 KB |
Output is correct |
7 |
Correct |
430 ms |
54168 KB |
Output is correct |
8 |
Correct |
363 ms |
43052 KB |
Output is correct |
9 |
Correct |
985 ms |
88884 KB |
Output is correct |
10 |
Correct |
450 ms |
57176 KB |
Output is correct |
11 |
Incorrect |
11 ms |
3452 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |