Submission #1051034

#TimeUsernameProblemLanguageResultExecution timeMemory
1051034ItamarSky Walking (IOI19_walk)C++14
0 / 100
17 ms11868 KiB
using namespace std; #include<vector> #include<map> #include<set> #define ll long long #define vll vector<ll> #define pll pair<ll,ll> #define pi pair<ll,ll> #include<cmath> #define vi vector<int> #include<algorithm> 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 g) { int n = x.size(), m = l.size(); if(n==1)return 0; vector<vi> in(2e5+2); vector<vi> out(2e5+2); map<ll,ll> dp; multiset<ll> se; se.insert(1e18+1); se.insert(-1e18-1); dp[1e18+1]=1e18; dp[-1e18-1]=1e18; for(int i = 0; i < m;i++){ dp[y[i]]=1e18; in[l[i]].push_back(y[i]); out[r[i]].push_back(y[i]); } out[0].push_back(0); dp[0]=0; se.insert(0); for(int i = 0; i < n; i++){ for(ll t : in[i])se.insert(t); for(ll t : out[i]){ if(i == n-1){ dp[0] = min(dp[0], dp[t]+t); } se.erase(se.find(t)); } for(ll t : out[i]){ auto it1 = se.lower_bound(t), it2 = se.upper_bound(t); it1--,it2++; dp[*it1] = min(dp[*it1],dp[t]+abs(*it1-t)); dp[*it2] = min(dp[*it2],dp[t]+abs(*it2-t)); } for(ll t : out[i])if(se.find(t) == se.end())dp[t] = 1e18; } if(dp[0] == 1e18)return -1; return dp[0]+x[n-1]-x[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...