Submission #790842

#TimeUsernameProblemLanguageResultExecution timeMemory
790842WLZAliens (IOI16_aliens)C++17
25 / 100
1764 ms1048576 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "../debug.h" #else #define debug(...) 0 #endif using ii = pair<int, int>; using ll = long long; using vi = vector<int>; using vll = vector<ll>; using vii = vector<ii>; const ll LINF = (ll) 1e18; /** * @brief Li Chao Tree with dynamically created nodes */ class li_chao_tree { private: struct line { int m; ll b; }; ll eval(const line &f, int x) { return (ll) f.m * x + f.b; } struct node { node *left, *right; line f; int l, r; node(int _l, int _r, const line &_f = {0, LINF}) : l(_l), r(_r), f(_f) { left = right = nullptr; } } *root; void add(node *cur, line nf) { int m = (cur->l + cur->r) / 2; bool bl = eval(nf, cur->l) < eval(cur->f, cur->l); bool bm = eval(nf, m) < eval(cur->f, m); if (bm) swap(cur->f, nf); if (cur->r - cur->l == 1) return; if (cur->left == nullptr) cur->left = new node(cur->l, m, cur->f); if (cur->right == nullptr) cur->right = new node(m, cur->r, cur->f); if (bl != bm) { add(cur->left, nf); } else { add(cur->right, nf); } } long long query(node *cur, int x) { if (cur == nullptr) return LINF; if (cur->r - cur->l == 1) return eval(cur->f, x); int m = (cur->l + cur->r) / 2; if (x < m) return min(eval(cur->f, x), query(cur->left, x)); else return min(eval(cur->f, x), query(cur->right, x)); } public: li_chao_tree(long long l, long long r) { root = new node(l, r); } void add(int m, long long b) { add(root, {m, b}); } long long query(long long x) { return query(root, x); } }; long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]); vii segments; for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]}); sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; }); vi nr = {segments[0].first}, nc = {segments[0].second}; for (int i = 1; i < n; i++) { if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) { nr.push_back(segments[i].first); nc.push_back(segments[i].second); } } swap(r, nr); swap(c, nc); n = (int) r.size(); debug(r, c); //vector<vll> dp(n + 1, vll(k + 1, LINF)); dp[0].assign(k + 1, 0); vector<li_chao_tree> lct(k + 1, li_chao_tree(0, 0)); for (int j = 0; j <= k; j++) lct[j] = li_chao_tree(0, m + 5); for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]); vll dp(k + 1, 0); dp[0] = LINF; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) dp[j] = lct[j - 1].query(c[i - 1]) + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1); if (i < n) for (int j = 0; j <= k; j++) { lct[j].add(-2 * r[i], dp[j] + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)); } } debug(dp); return dp[k]; }

Compilation message (stderr)

aliens.cpp: In constructor 'li_chao_tree::node::node(int, int, const li_chao_tree::line&)':
aliens.cpp:29:14: warning: 'li_chao_tree::node::r' will be initialized after [-Wreorder]
   29 |       int l, r;
      |              ^
aliens.cpp:28:12: warning:   'li_chao_tree::line li_chao_tree::node::f' [-Wreorder]
   28 |       line f;
      |            ^
aliens.cpp:30:7: warning:   when initialized here [-Wreorder]
   30 |       node(int _l, int _r, const line &_f = {0, LINF}) : l(_l), r(_r), f(_f) {
      |       ^~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0
      |                    ^
aliens.cpp:87:3: note: in expansion of macro 'debug'
   87 |   debug(r, c);
      |   ^~~~~
aliens.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0
      |                    ^
aliens.cpp:99:3: note: in expansion of macro 'debug'
   99 |   debug(dp);
      |   ^~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...