#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
//#define int long long
#define ii pair<long long,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define mid (l+r)/2
#define inf 1e15
#define MOD 1000000007
#define MX 100005
using namespace std;
struct fenwick{
vi arr;
fenwick(int n){
arr.resize(n+1, 0);
}
void update(int pos, int val){
for(int i=pos;i<arr.size();i+=(i&(-i))){
arr[i]+=val;
}
}
int query(int l, int r){
int ans = 0;
for(int i=r;i>0;i-=(i&(-i))){
ans+=arr[i];
}
for(int i=l-1;i>0;i-=(i&(-i))){
ans-=arr[i];
}
}
};
map<ii, vii> edges;
map<ii, int> dist;
int dijkstra(ii s, ii t){
priority_queue<pair<int, ii>, vector<pair<int, ii>>, greater<pair<int, ii>>> pq;
dist[s] = 0;
pq.push({0, s});
while(pq.size()){
auto u = pq.top(); pq.pop();
if(u.nd==t) break;
if(u.st > dist[u.nd]) continue;
for(auto p:edges[u.nd]){
if(dist[p] > u.st + abs(u.nd.st-p.st) + abs(u.nd.nd-p.nd)){
dist[p] = u.st + abs(u.nd.st-p.st) + abs(u.nd.nd-p.nd);
pq.push({dist[p], p});
}
}
}
return dist[t];
}
int64_t min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g){
int bn = x.size(), sn = l.size();
set<int> temp;
vi yind={0};
for(int i=0; i<bn; i++) temp.insert(h[i]);
for(int i=0; i<sn; i++) temp.insert(y[i]);
map<int, int> inv;
for(auto i:temp){
inv[i] = yind.size();
yind.pb(i);
}
map<int, vi> lef, rig;
for(int i=0; i<sn; i++){
lef[l[i]].pb(i);
rig[r[i]].pb(i);
}
vi bpoi[bn], spoi[sn];
set<ii> cur;
for(int i=0; i<bn; i++){
bpoi[i].pb(0);
dist[{x[i], 0}] = INT_MAX;
//open
for(auto j:lef[i]){
//cerr << "opening" spc y[j] << endl;
cur.insert({y[j],j});
}
//count
for(auto j:cur){
if(j.st>h[i]) break;
bpoi[i].pb(j.st);
spoi[j.nd].pb(x[i]);
dist[{x[i], j.st}]=INT_MAX;
}
for(int j=0; j<bpoi[i].size()-1; j++){
edges[{x[i], bpoi[i][j]}].pb({x[i], bpoi[i][j+1]});
edges[{x[i], bpoi[i][j+1]}].pb({x[i], bpoi[i][j]});
//cerr << x[i] spc bpoi[i][j] spc "to" spc x[i] spc bpoi[i][j+1] << endl;
}
//close
for(auto j:rig[i]){
//cerr << "closing" spc y[j] << endl;
cur.erase({y[j],j});
}
}
for(int i=0; i<sn; i++){
for(int j=0; j<spoi[i].size()-1; j++){
edges[{spoi[i][j], y[i]}].pb({spoi[i][j+1], y[i]});
edges[{spoi[i][j+1], y[i]}].pb({spoi[i][j], y[i]});
//cerr << spoi[i][j] spc y[i] spc "to" spc spoi[i][j+1] spc y[i] << endl;
}
}
return dijkstra({x[s], 0}, {x[g], 0});
}
Compilation message
walk.cpp: In member function 'void fenwick::update(int, int)':
walk.cpp:26:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for(int i=pos;i<arr.size();i+=(i&(-i))){
| ~^~~~~~~~~~~
walk.cpp: In member function 'int fenwick::query(int, int)':
walk.cpp:38:5: warning: no return statement in function returning non-void [-Wreturn-type]
38 | }
| ^
walk.cpp: In function 'int64_t min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int32_t, int32_t)':
walk.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int j=0; j<bpoi[i].size()-1; j++){
| ~^~~~~~~~~~~~~~~~~
walk.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int j=0; j<spoi[i].size()-1; j++){
| ~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
937 ms |
218356 KB |
Output is correct |
| 4 |
Incorrect |
1069 ms |
262088 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
128 ms |
28940 KB |
Output is correct |
| 2 |
Runtime error |
2578 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
128 ms |
28940 KB |
Output is correct |
| 2 |
Runtime error |
2578 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
