This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define gg exit(0);
const long long INF=1e9+10;
const int N=100010;
int f[N];
vector<int> val;
multiset<int> up[N],dw[N];
void upd_u(int i,int j,int t){
i=lower_bound(all(val),i)-val.begin()+1;
for(;i;i-=i&-i){
if(t) up[i].insert(j); else up[i].erase(up[i].find(j));
}
}
void upd_d(int i,int j,int t){
i=lower_bound(all(val),i)-val.begin()+1;
for(;i<=val.size();i+=i&-i){
if(t) dw[i].insert(j); else dw[i].erase(dw[i].find(j));
}
}
int que_u(int i){
i=lower_bound(all(val),i)-val.begin()+1;
int ret=INF;
for(;i<=val.size();i+=i&-i) if(up[i].size())
ret=min(ret,*up[i].begin());
return ret;
}
int que_d(int i){
i=lower_bound(all(val),i)-val.begin()+1;
int ret=INF;
for(;i;i-=i&-i) if(dw[i].size())
ret=min(ret,*dw[i].begin());
return ret;
}
long long min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g){
/// noi toa nha l va r o do cao y
/**
_________
________
f_i = f_j + x[l_i] - x[l_j] + abs(y_i-y_j)
x[l_i] + y_i + f_j - x[l_j] - y_j
*/
val=y, val.pb(0), sort(all(val)), val.erase(unique(all(val)),val.end());
vector<ii> q;
forinc(i,1,l.size()){
q.push_back({l[i-1],-i});
q.push_back({r[i-1],i});
}
q.push_back({0,l.size()+1});
q.push_back({0,-l.size()-1});
sort(all(q));
y.emplace_back();
x.push_back(x[0]);
l.push_back(0);
r.push_back(0);
int ret=INF;
forv(i,q){
//cerr<<i.fi<<" "<<i.se<<"\n";
if(i.se<0){ i.se=-i.se;
i.se--;
f[i.se]=min(x[l[i.se]]+y[i.se]+que_d(y[i.se]),x[l[i.se]]-y[i.se]+que_u(y[i.se]));
if(i.se==l.size()-1) f[i.se]=0;
//cerr<<f[i.se]<<"\n";
if(f[i.se]<0){
//cerr<<x[l[i.se]]+y[i.se]+que_d(y[i.se]);
gg
}
upd_d(y[i.se],f[i.se]-x[l[i.se]]-y[i.se],1);
upd_u(y[i.se],f[i.se]-x[l[i.se]]+y[i.se],1);
if(r[i.se]==x.size()-2){
ret=min(ret,f[i.se]+x[r[i.se]]-x[l[i.se]]+y[i.se]);
//cerr<<f[i.se];
}
} else{
i.se--;
upd_d(y[i.se],f[i.se]-x[l[i.se]]-y[i.se],0);
upd_u(y[i.se],f[i.se]-x[l[i.se]]+y[i.se],0);
}
}
return ret;
}
Compilation message (stderr)
walk.cpp: In function 'void upd_d(int, int, int)':
walk.cpp:35:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;i<=val.size();i+=i&-i){
~^~~~~~~~~~~~
walk.cpp: In function 'int que_u(int)':
walk.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;i<=val.size();i+=i&-i) if(up[i].size())
~^~~~~~~~~~~~
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:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i.se==l.size()-1) f[i.se]=0;
~~~~^~~~~~~~~~~~
walk.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(r[i.se]==x.size()-2){
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |