Submission #790127

#	Time	Username	Problem	Language	Result	Execution time	Memory
790127		WLZ	Aliens (IOI16_aliens)	C++17	25 / 100	1629 ms	1048576 KiB

aliens

#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 { long long m, b; };
    long long eval(const line &f, long long x) { return f.m * x + f.b; }
    struct node {
      node *left, *right;
      line f;
      long long l, r;
      node(long long _l, long long _r) : l(_l), r(_r) {
        left = right = nullptr;
        f = {0, LINF};
      }
    } *root;
 
    void add(node *cur, line nf) {
      long long 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 (bl != bm) {
        if (cur->left == nullptr) cur->left = new node(cur->l, m);
        add(cur->left, nf);
      } else {
        if (cur->right == nullptr) cur->right = new node(m, cur->r);
        add(cur->right, nf);
      }
    }
 
    long long query(node *cur, long long x) {
      if (cur == nullptr) return LINF;
      if (cur->r - cur->l == 1) return eval(cur->f, x);
      long long 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(long long 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, 2 * m);
  for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) dp[i][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[i][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[n][k];
}

Compilation message (stderr)

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:88:3: note: in expansion of macro 'debug'
   88 |   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);
      |   ^~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40