Submission #790973

#	Time	Username	Problem	Language	Result	Execution time	Memory
790973		WLZ	Aliens (IOI16_aliens)	C++17	25 / 100	4 ms	472 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;
 
class convex_hull {
  private:
    vector<long long> a, b;
    vector<int> id;
    int ptr = 0;
 
    int bad(int l1, int l2, long long _a, long long _b) {
      if ((a[l1] == _a) && (b[l1] == _b)) return 1;
      return ((_b - b[l1]) * (a[l1] - a[l2]) > (b[l2] - b[l1]) * (a[l1] - _a));
    }
  public:
    void add(long long _a, long long _b, int _id) {
      while ((int) a.size() >= 2 && bad((int) a.size() - 1, (int) a.size() - 2, _a, _b)) {
        a.pop_back();
        b.pop_back();
        id.pop_back();
      }
      a.push_back(_a);
      b.push_back(_b);
      id.push_back(_id);
    }
 
    pair<int, long long> query(long long x) {
      if (ptr >= (int) a.size()) {
        ptr = (int) a.size() - 1;
      }
      while (ptr < (int) a.size() - 1 && a[ptr + 1] * x + b[ptr + 1] >= a[ptr] * x + b[ptr]) {
        ptr++;
      }
      return {id[ptr], a[ptr] * x + b[ptr]};
    }
};

pair<ll, int> solve(int n, int m, const vi &r, const vi &c, ll cost) {
  convex_hull ch;
  ch.add(-(-2 * r[0]), -((ll) r[0] * r[0] - 2 * r[0]), 0);
  for (int i = 1; i <= n; i++) {
    auto p = ch.query(c[i - 1]);
    ll best = -p.second + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1) + cost;
    if (i == n) return {best, p.first + 1};
    ch.add(-(-2 * r[i]), -(best + (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)), p.first + 1);
  }
}

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();
  ll lo = 0, hi = (ll) 2 * m * m;
  for (int i = 35; i >= 0; i--) {
    auto p = solve(n, m, r, c, lo + (1ll << i));
    if (p.second >= k) lo += (1ll << i);
  }
  auto p1 = solve(n, m, r, c, lo), p2 = solve(n, m, r, c, lo + 1);
  p1.first -= lo * p1.second;
  p2.first -= (lo + 1) * p2.second;
  if (p1.second == p2.second) return p1.first;
  return p1.first + (p1.second - k) * (p2.first - p1.first) / (p1.second - p2.second);
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:79:14: warning: unused variable 'hi' [-Wunused-variable]
   79 |   ll lo = 0, hi = (ll) 2 * m * m;
      |              ^~
aliens.cpp: In function 'std::pair<long long int, int> solve(int, int, const vi&, const vi&, ll)':
aliens.cpp:53:15: warning: control reaches end of non-void function [-Wreturn-type]
   53 |   convex_hull ch;
      |               ^~

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