Submission #525648

#	Time	Username	Problem	Language	Result	Execution time	Memory
525648		Sunset	Aliens (IOI16_aliens)	C++17	100 / 100	386 ms	12720 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

#define mp make_pair
#define sz(x) ((int)((x).size()))
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ipair;
typedef pair <ll, ll> lpair;
const int IINF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = numeric_limits<double>::infinity();
const double DNAN = numeric_limits<double>::quiet_NaN();
const double EPS = 1e-9;
const double PI = acos((double)-1.0);
const int DX[] = { 1,  0, -1,  0,  1, -1,  1, -1};
const int DY[] = { 0,  1,  0, -1,  1, -1, -1,  1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll sqr(ll x) { return x*x; } ll sqr(int x) { return (ll)x*x; }
double sqr(double x) { return x*x; }
mt19937 mmtw(960172);
ll rnd(ll x, ll y) { static uniform_int_distribution<ll> d; return d(mmtw) % (y - x + 1) + x; }

template<typename T, typename M> T& updMin(T& a, M const& b) { if (b < a) a = b; return a; }
template<typename T, typename M> T& updMax(T& a, M const& b) { if (a < b) a = b; return a; }

ll divFloor(ll a, ll b) { if (b < 0) { a = -a; b = -b; } return a >= 0 ? a / b : (a - b + 1) / b; }
ll divCeil(ll a, ll b) { if (b < 0) { a = -a; b = -b; } return a >= 0 ? (a + b - 1) / b : a / b; }
ll divFloorS(ll a, ll b) { if (b < 0) { a = -a; b = -b; } return a >= 0 ? (a + b - 1) / b - 1 : a / b - 1; }
ll divCeilS(ll a, ll b) { if (b < 0) { a = -a; b = -b; } return a >= 0 ? a / b + 1 : (a - b + 1) / b + 1; }
template<typename T> T pw(T a, ll b) { T r = T(1); if (b <= 0) return r; for (;; b >>= 1) { if (b & 1) r *= a; if (b) a *= a; else return r; } }

template<typename T> void unique(vector<T> &a) { sort(all(a)); a.erase(unique(all(a)), a.end()); }
template<typename T> int lowerBound(vector<T> const& a, T const& x) { return lower_bound(all(a), x) - a.begin(); }
template<typename T> int upperBound(vector<T> const& a, T const& x) { return upper_bound(all(a), x) - a.begin(); }

template<typename K, typename V> V getOrDef(map<K, V> const& a, K const& k, V const& def = V()) { auto it = a.find(k); return it == a.end() ? def : it->second; }
template<typename K, typename V> V getOrDef(unordered_map<K, V> const& a, K const& k, V const& def = V()) { auto it = a.find(k); return it == a.end() ? def : it->second; }
template<typename T> T getOrDef(vector<T> const& a, int i, T const& def = T()) { return i < 0 || i >= sz(a) ? def : a[i]; }
template<typename T> T getOrDef(vector<vector<T>> const& a, int i, int j, T const& def = T()) { return i < 0 || i >= sz(a) ? def : getOrDef(a[i], j, def); }
template<typename T> T backOrDef(vector<T> const& a, T const& def = T()) { return a.empty() ? def : a.back(); }

template<typename A, typename B> istream& operator >> (istream& in, pair<A, B>& p) { return in >> p.X >> p.Y; }
template<typename A, typename B> ostream& operator << (ostream& out, pair<A, B> const& p) { return out << p.X << " " << p.Y; }
template<typename T> istream& operator >> (istream& in, vector<T>& a) { for (T& x : a) in >> x; return in; }
template<typename T> ostream& operator << (ostream& out, vector<T> const& a) {
  bool f = true;
  for (T const& x : a) {
    if (!f) out << " ";
    f = false; out << x;
  }
  return out;
}
template<typename T> ostream& operator << (ostream& out, vector<vector<T>> const& a) {
  for (vector<T> const& x : a) out << x << "\n";
  return out;
}

template<typename T> bool isZero(T const& x) { return x == T(0); }
bool isZero(float x) { return abs(x) < EPS; }
bool isZero(double x) { return abs(x) < EPS; }
bool isZero(long double x) { return abs(x) < EPS; }
template<typename T> int sgn(T const& x) { if (isZero(x)) return 0; return x > 0 ? 1 : -1; }

template<typename T>
class LinearMaxInc {
  struct Seg {
    T x0, k, b;
    int index;
  };
  vector<Seg> segs;
public:
  LinearMaxInc() = default;
  explicit LinearMaxInc(vector<pair<T, T>> const& a) {
    vector<int> order(sz(a));
    iota(all(order), 0);
    sort(all(order), [&](int x, int y) { return a[x].first < a[y].first; });
    for (int i : order) add(a[i].first, a[i].second, i);
  }

  void add(T const& k, T const& b, int index = -1) {
    assert(segs.empty() || segs.back().k <= k);
    while (true) {
      if (segs.empty()) {
        segs.push_back({numeric_limits<T>::lowest(), k, b, index});
        return;
      }
      Seg const& s = segs.back();
      if (s.k == k) {
        if (s.b >= b) return;
        segs.pop_back();
        continue;
      }
      T x0 = (s.b - b + (numeric_limits<T>::is_integer && s.b - b >= 0 ? k - s.k - 1 : 0)) / (k - s.k);
      if (s.x0 >= x0)
        segs.pop_back();
      else {
        segs.push_back({x0, k, b, index});
        return;
      }
    }
  }

  pair<T, int> getMax(T const& x) const {
    if (segs.empty()) return {numeric_limits<T>::lowest(), -1};
    int cl = 0, cr = sz(segs);
    while (cr - cl > 1) {
      int mid = (cl + cr) / 2;
      (x < segs[mid].x0 ? cr : cl) = mid;
    }
    return {segs[cl].k * x + segs[cl].b, segs[cl].index};
  }
};

long long take_photos(int n, int, int k, std::vector<int> cx, std::vector<int> cy) {
  vector<ipair> segs;
  for (int i = 0; i < n; ++i) {
    int x = cx[i], y = cy[i];
    if (x > y) swap(x, y);
    ++y;
    segs.push_back({x, y});
  }
  sort(all(segs), [](ipair const& a, ipair const& b) {
    if (a.Y != b.Y) return a.Y < b.Y;
    return a.X > b.X;
  });
  {
    vector<ipair> segs2;
    for (ipair s : segs) {
      while (!segs2.empty() && segs2.back().X >= s.X)
        segs2.pop_back();
      segs2.push_back(s);
    }
    segs = move(segs2);
  }

  n = sz(segs);
  k = min(k, n);
  ll ans = -1;

  ll cl = -1.1e12, cr = 1.1e12;
  while (cr - cl > 1) {
    ll lambda = (cl + cr) / 2;
    vector<pair<ll, int>> d(n + 1);
    d[0] = {0, 0};
    LinearMaxInc<ll> lm;
    for (int i = 0; i <= n; ++i) {
      if (i != 0) {
        auto nd = lm.getMax(segs[i - 1].Y);
        d[i] = {-nd.X + sqr(segs[i - 1].Y) - lambda, nd.Y};
      }
      if (i != n) {
        lm.add(2 * segs[i].X, -d[i].X + (i == 0 ? 0LL : sqr(max(0, segs[i - 1].Y - segs[i].X))) - sqr(segs[i].X), d[i].Y + 1);
      }
    }
    updMax(ans, d[n].X + lambda * k);
    if (d[n].Y < k)
      cl = lambda;
    else
      cr = lambda;
  }

  return ans;
}

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