Submission #731297

#TimeUsernameProblemLanguageResultExecution timeMemory
731297danikoynovSky Walking (IOI19_walk)C++14
33 / 100
213 ms20796 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; struct skywalk { int left, right; ll height; skywalk(int _left = 0, int _right = 0, ll _height = 0) { left = _left; right = _right; height = _height; } }sky[maxn]; bool cmp(const skywalk &sk1, const skywalk &sk2) { return sk1.height < sk2.height; } const ll inf = 1e18; struct node { ll down_sum, up_sum; node(ll _down_sum = inf, ll _up_sum = inf) { down_sum = _down_sum; up_sum = _up_sum; } }; node merge_nodes(node lf, node rf) { node nd; nd.down_sum = min(lf.down_sum, rf.down_sum); nd.up_sum = min(lf.up_sum, rf.up_sum); return nd; } node tree[4 * maxn]; int is_active[maxn]; ll dp[maxn]; void toggle(int root, int left, int right, int pos) { if (left == right) { is_active[left] ^= 1; ///cout << root << " : " << left << " : " << right << " : " << pos << " " << is_active[left] << endl; if (is_active[left]) { tree[root].down_sum = - sky[left].height + dp[left]; tree[root].up_sum = sky[left].height + dp[left]; ///cout << "activate " << left << " " << sky[left].height << endl; } else { tree[root] = node(); } return; } int mid = (left + right) / 2; if (pos <= mid) toggle(root * 2, left, mid, pos); else toggle(root * 2 + 1, mid + 1, right, pos); tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]); ///cout << "here " << left << " " << right << " " << tree[root].up_sum << endl; } node query(int root, int left, int right, int qleft, int qright) { if (left > qright || right < qleft) return node(); if (left >= qleft && right <= qright) return tree[root]; int mid = (left + right) / 2; return merge_nodes(query(root * 2, left, mid, qleft, qright), query(root * 2 + 1, mid + 1, right, qleft, qright)); } int n, m; ll x[maxn], h[maxn]; vector < pair < int, int > > upd[maxn]; ll state[100][100]; bool intersects(int idx, int pos) { if (sky[idx].left <= pos && sky[idx].right >= pos && sky[idx].height <= h[pos]) return true; return false; } void relax_state(int i) { for (int p1 = 0; p1 < m; p1 ++) { if (!intersects(p1, i)) continue; for (int p2 = 0; p2 < m; p2 ++) { if (!intersects(p2, i)) continue; state[i][p2] = min(state[i][p2], state[i][p1] + abs(sky[p1].height - sky[p2].height)); } } } long long min_distance(vector<int> X, vector<int> H, vector<int> l, vector<int> r, vector<int> y, int s, int g) { n = X.size(); m = l.size(); for (int i = 0; i < n; i ++) x[i] = X[i], h[i] = H[i]; for (int i = 0; i < m; i ++) { sky[i] = skywalk(l[i], r[i], y[i]); } sort(sky, sky + m, cmp); if (n <= 50 && m <= 50) { if (s > g) swap(s, g); /**cout << "skywalk" << endl; for (int j = 0; j < m; j ++) { cout << j << " : " << sky[j].left << " " << sky[j].right << " " << sky[j].height << endl; } cout << "------------" << endl;*/ for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) state[i][j] = inf; for (int j = 0; j < m; j ++) { if (intersects(j, s)) state[s][j] = sky[j].height; } for (int i = s - 1; i >= 0; i --) { for (int j = i + 1; j <= s; j ++) { for (int p = 0; p < m; p ++) { if (intersects(p, i) && intersects(p, j)) { state[i][p] = min(state[i][p], state[j][p] + abs(x[j] - x[i])); } } } relax_state(i); } /**for (int j = 0; j < m; j ++) cout << state[s][j] << " "; cout << endl;*/ for (int i = 0; i < n; i ++) { for (int j = 0; j < i; j ++) { for (int p = 0; p < m; p ++) { if (intersects(p, i) && intersects(p, j)) { state[i][p] = min(state[i][p], state[j][p] + abs(x[j] - x[i])); } } } relax_state(i); } /**for (int i = n - 1; i >= g; i --) { for (int j = n - 1; j > i; j --) { for (int p = 0; p < m; p ++) { if (intersects(p, i) && intersects(p, j)) { state[i][p] = min(state[i][p], state[j][p] + abs(x[j] - x[i])); } } } relax_state(i); }*/ ll ans = inf; for (int j = 0; j < m; j ++) { if (state[g][j] != inf) ans = min(ans, state[g][j] + sky[j].height); } if (ans == inf) return -1; return ans; } if (s != 0 || g != n - 1) return 0; for (int i = 0; i < m; i ++) { upd[sky[i].left].push_back({i, 1}); } for (int i = 0; i < m; i ++) { upd[sky[i].right].push_back({i, -1}); } for (pair < int, int > cur : upd[s]) { dp[cur.first] = sky[cur.first].height; toggle(1, 0, m - 1, cur.first); ///cout << "here" << endl; } ///cout << tree[1].up_sum << endl; for (int i = 1; i < g; i ++) { for (pair < int, int > cur : upd[i]) { if (cur.second == 1) { node under = node(), above = node(); if (cur.first != 0) under = query(1, 0, m - 1, 0, cur.first - 1); if (cur.first != m - 1) above = query(1, 0, m - 1, cur.first + 1, m - 1); //cout << under.down_sum << " " << above.up_sum << endl; if (under.down_sum == inf && above.up_sum == inf) dp[cur.first] = inf; else dp[cur.first] = min(sky[cur.first].height + under.down_sum, above.up_sum - sky[cur.first].height); ///cout << cur.first << " :: " << dp[cur.first] << endl; } toggle(1, 0, m - 1, cur.first); } } node ans = tree[1]; if (ans.up_sum == inf) return -1; return ans.up_sum + x[g] - x[s]; }

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:134:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  134 |         if (s > g)
      |         ^~
walk.cpp:143:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  143 |             for (int i = 0; i < n; i ++)
      |             ^~~
#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...