Submission #1051030

#TimeUsernameProblemLanguageResultExecution timeMemory
1051030ItamarSky Walking (IOI19_walk)C++14
0 / 100
28 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<int,ll> dp; multiset<ll> se; se.insert(1e18+1); 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(int t : in[i])se.insert(t); for(int t : out[i]){ if(i == n-1){ dp[0] = min(dp[0], dp[t]+t); } se.erase(se.find(t)); } for(int 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(int 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]; }

Compilation message (stderr)

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:20:12: warning: overflow in conversion from 'double' to 'std::map<int, long long int>::key_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   20 |     dp[1e18+1]=1e18;
      |        ~~~~^~
#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...