Submission #529389

#	Time	Username	Problem	Language	Result	Execution time	Memory
529389		msg555	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	292 KiB

aliens

#include "aliens.h"

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

const long long INF = 0x3FFFFFFFFFFFFFFFLL;

long long squared(int x) {
  return 1ll * x * x;
}

long long cross_x(pair<long long, long long> X, pair<long long, long long> Y) {
  /* Returns the first x >= to when the lines intersect */
  long long db = X.first - Y.first;
  long long dc = Y.second - X.second;
  if (db == 0) {
    return db < 0 ? -INF : INF;
  }
  if (db < 0) {
    db = -db;
    dc = -dc;
  }
  if (dc < 0) {
    return dc / db;
  }
  return (dc + db - 1) / db;
}

struct dumb_hull {
  bool insert(long long a, long long b) {
    lns.push_back(make_pair(a, b));
    return true;
  }

  long long get(long long x) const {
    long long res = -INF;
    for (auto ln : lns) {
      res = max(res, ln.first * x + ln.second);
    }
    return res;
  }

  vector<pair<long long, long long> > lns;
};

struct line_hull {
  /* Implements a max hull, get the max ax+b for all inserted lines. */

  bool insert(long long a, long long b) {
    /* Insert line ax+b */
    // cout << "INSERT " << a << ", " << b << endl;
    auto ln = make_pair(a, b);
    auto it = st.lower_bound(ln);
    bool is_last = it == st.end();
    if (!is_last && ln.first == it->first) {
      return false;
    }

    auto jt = it;
    bool is_first = it == st.begin();
    if (!is_first) {
      --it;  
      if (it->first == ln.first) {
        if (it == st.begin()) {
          is_first = true;
        } else {
          --it;
        }
      }
    }

    long long lft_x = is_first ? -INF : cross_x(*it, ln);
    long long rht_x = is_last ? INF : cross_x(ln, *jt);
    if (rht_x <= lft_x) {
      return false;
    }

    if (!is_first) {
      while (it != st.begin()) {
        auto kt = it--;
        long long prev_lft_x = cross_x(*it, *kt);
        if (prev_lft_x < lft_x) {
          ++it;
          break;
        }
        lft_x = cross_x(*it, ln);
      }
      ++it;
    }

    if (!is_last) {
      while (true) {
        auto kt = jt++;
        if (jt == st.end()) {
          break;
        }
        
        long long prev_rht_x = cross_x(*kt, *jt);
        if (rht_x < prev_rht_x) {
          break;
        }
        rht_x = prev_rht_x;
      }
      --jt;
    }

    crs.erase(
      crs.lower_bound(make_pair(lft_x + (is_first ? -1 : 0), make_pair(INF, INF))),
      crs.lower_bound(make_pair(rht_x, make_pair(INF, INF)))
    );
    crs.insert(make_pair(lft_x, ln));
    if (!is_last) {
      crs.insert(make_pair(rht_x, *jt));
    }
    st.erase(it, jt);
    st.insert(ln);

    // cout << st.size() << ", " << crs.size() << endl;

    return true;
  }

  long long get(long long x) const {
    auto it = crs.lower_bound(make_pair(x, make_pair(-INF, -INF)));
    --it;
    return it->second.first * x + it->second.second;
  }

  set<pair<long long, long long> > st;
  set<pair<long long, pair<long long, long long> > > crs;
};

long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
  vector<pair<int, int> > A;
  for (int i = 0; i < N; i++) {
    int ri = R[i];
    int ci = C[i];
    if (ri > ci) swap(ri, ci);
    A.push_back(make_pair(ci, ci - ri));
  }
  sort(A.begin(), A.end());

  int j = 0;
  for (auto p : A) {
    while (j > 0 && p.second >= A[j - 1].second + p.first - A[j - 1].first) {
      --j;
    }
    A[j++] = p;
  }
  A.resize(j);
  N = j;

  vector<long long> ADJ(N + 1, 0);
  for (int i = 1; i < N; i++) {
    ADJ[i] = squared(max(0, 1 + A[i].second - A[i].first + A[i - 1].first));
  }

  long long INF = squared(M + 1);
  vector<long long> DP(N + 1, INF);
  vector<long long> DP2(N + 1, INF);
  DP[0] = 0;

  for (int k = 0; k < K; k++) {
    line_hull hl;
    //dumb_hull hl;
    for (int i = 0; i <= N; i++) {
      if (i) {
        long long x = A[i - 1].first;
        DP[i] = -hl.get(x) + squared(x);
      }

/*
      for (int j = 0; j < i; j++) {
        DP[i] = min(
          DP[i],
          DP[j] + squared(1 + A[j].second + A[i - 1].first - A[j].first) - ADJ[j]
        );
      }
*/

      // x^2 + bx + c where x = A[i - 1].first
      long long sadd = 1 + A[i].second - A[i].first;
      long long b = 2 * sadd;
      long long c = squared(sadd) + DP[i] - ADJ[i];
      hl.insert(-b, -c);
    }
    DP.swap(DP2);
  }
  
  return DP[N];
}

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