Submission #136343

#	Time	Username	Problem	Language	Result	Execution time	Memory
136343		MAMBA	Aliens (IOI16_aliens)	C++17	100 / 100	312 ms	6416 KiB

aliens

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

using namespace std;

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, long long> pil;
typedef pair<ll, ll> pll;

#define BB dq[dq.size() - 2]

struct Line {
  ll cf, b, z;
  Line(ll cf_, ll b_, ll z_) {
    cf = cf_;
    b = b_;
    z = z_;
  }
};

inline pll inter(Line a, Line b) { return pll(a.b - b.b, b.cf - a.cf); }

inline bool cmp(pll a, pll b) {
  if (a.second < 0) {
    a.second *= -1;
    a.first *= -1;
  }
  if (b.second < 0) {
    b.second *= -1;
    b.first *= -1;
  }

  return a.first * b.second < a.second * b.first;
}

inline bool cmp(pll a, ll b) { return cmp(a, pll(b, 1)); }

inline bool equ(pll a, ll b) {
  return !cmp(a, pll(b, 1)) && !cmp(pll(b, 1), a);
}

ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
  vi ind;
  int N = 0;

  {
    rep(i, 0, n) {
      if (r[i] > c[i]) swap(r[i], c[i]);
      c[i]++;
    }

    vi local(n);
    iota(all(local), 0);
    sort(all(local), [&](int a, int b) {
      if (r[a] != r[b]) return r[a] < r[b];
      return c[a] > c[b];
    });

    int mx = -1;
    rep(i, 0, n) if (c[local[i]] > mx) {
      ind.pb(local[i]);
      mx = c[local[i]];
    }
    N = ind.size();
    ind.pb(n);
    r.push_back(1e9);

    if (k == 1) {
      ll dist = c[ind[N - 1]] - r[ind[0]];
      return dist * dist;
    }
  }

  auto solve = [&](ll Cost) -> pil {
    vector<pil> dp(N + 1);
    deque<Line> dq;
    dp[N] = pil(0, 0);

    auto push = [&](int id) {
      int pos = ind[id];
      int pre = ind[id - 1];

      ll Rj1 = c[pre];
      ll Li = r[pos];

      Line ln(
          Rj1,
          dp[id].second + Rj1 * Rj1 - (Li < Rj1 ? (Rj1 - Li) * (Rj1 - Li) : 0),
          dp[id].first);

      while (dq.size() > 1 && cmp(inter(BB, ln), inter(BB, dq.back())))
        dq.pop_back();
      dq.pb(ln);
      return;
    };

    auto relax = [&](int id) {
      ll pn = -2ll * r[ind[id]];
      while (dq.size() > 1 && cmp(inter(dq[0], dq[1]), pn)) dq.pop_front();
      if (dq.size() > 2 && equ(inter(dq[0], dq[1]), pn) &&
          equ(inter(dq[1], dq[2]), pn)) {
        if (dq[0].z < dq[1].z) swap(dq[0], dq[1]);
        dq.pop_front();
      }
      return;
    };

    for (int i = N - 1; ~i; i--) {
      push(i + 1);
      relax(i);
      int me = ind[i];
      dp[i] = pil(dq[0].z + 1, (1ll * r[me] * r[me]) - 2ll * r[me] * dq[0].cf +
                                   dq[0].b + Cost);
      if (dq.size() > 1) {
        pil w(dq[1].z + 1,
              (1ll * r[me] * r[me]) - 2ll * r[me] * dq[1].cf + dq[1].b + Cost);
        if (w.second == dp[i].second && w.first < dp[i].first) dp[i] = w;
      }
    }

    return dp[0];
  };

  ll lo = 1ll * m * m + 10, hi = -1;

  while (lo - 1 != hi) {
    ll mid = lo + hi >> 1;
    if (k <= solve(mid).first)
      hi = mid;
    else
      lo = mid;
  }

  auto result = solve(lo);
  return result.second - k * lo;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:132:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     ll mid = lo + hi >> 1;
              ~~~^~~~

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