Submission #1242379

#TimeUsernameProblemLanguageResultExecution timeMemory
1242379nvujicaSky Walking (IOI19_walk)C++20
0 / 100
16 ms7240 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ll long long #include "walk.h" using namespace std; const int maxn = 1e5 + 10; const ll inf = (1LL << 60); vector<int> poc[maxn]; vector <int> kraj[maxn]; set <pair<int, ll> > s; set <pair<int, ll> > s2; ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int g) { int n = x.size(); int m = l.size(); ll ans = x[n - 1] - x[0]; for(int i = 0; i < m; i++){ poc[l[i]].push_back(y[i]); kraj[r[i] + 1].push_back(y[i]); } for(int i = 0; i < poc[0].size(); i++){ int vis = poc[0][i]; s.insert({vis, vis}); } for(int i = 1; i < n; i++){ if(s.empty()) return -1; for(int j = 0; j < poc[i].size(); j++){ int vis = poc[i][j]; ll cost = inf; auto it = s.lower_bound({vis, 0}); if(it != s.end()) cost = (*it).se + (*it).fi - vis; if(it != s.begin()){ it--; cost = min(cost, (*it).se + vis - (*it).fi); } s.insert({vis, cost}); } for(int j = 0; j < kraj[i].size(); j++){ int vis = kraj[i][j]; auto it = s.lower_bound({vis, 0}); ll cost = (*it).se; it++; if(it != s.end()){ ll c = cost + (*it).fi - vis; if(c < (*it).se){ int vis2 = (*it).fi; s.erase(it); s.insert({vis2, c}); } // (*it).se = min((*it).se, cost + (*it).fi - vis); } it = s.lower_bound({vis, 0}); if(it != s.begin()){ it--; ll c = cost + vis - (*it).fi; //(*it).se = min((*it).se, cost + vis - (*it).fi); if(c < (*it).se){ int vis2 = (*it).fi; s.erase(it); s.insert({vis2, c}); } it++; } s.erase({vis, cost}); } } if(s.empty()) return -1; ll naj = inf; auto it = s.begin(); while(it != s.end()){ naj = min(naj, (*it).fi + (*it).se); it++; } return ans + naj; }
#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...