Submission #816230

#	Time	Username	Problem	Language	Result	Execution time	Memory
816230		jun6873	Aliens (IOI16_aliens)	C++17	100 / 100	796 ms	165348 KiB

aliens

#include <bits/stdc++.h>

#include "aliens.h"
using namespace std;

using lint = long long;
using pint = pair<lint, lint>;
#define x first
#define y second

const lint inf = 1e18;

const int noden = 500004 * 20;
const lint rangel = 0, ranger = 1000000;
struct line {
  line() : a(0), b(inf) {}
  line(lint a, lint b) : a(a), b(b) {}
  lint operator()(lint x) { return a * x + b; }
  lint a, b;
};

struct lichao {
  line f[noden];
  int t[noden], lc[noden], rc[noden], cnt = 1;

  void init() {
    for (int i = 1; i <= cnt; i++) {
      f[i] = line();
      t[i] = lc[i] = rc[i] = 0;
    }
    cnt = 1;
  }

  void update(lint s, lint e, int x, line g, int v) {
    if (g(s) < f[x](s)) swap(f[x], g), swap(t[x], v);
    if (f[x](e) <= g(e)) return;

    lint m = (s + e) / 2;
    if (g(m) < f[x](m)) {
      swap(f[x], g);
      swap(t[x], v);
      if (!lc[x]) lc[x] = ++cnt;
      update(s, m, lc[x], g, v);
    } else {
      if (!rc[x]) rc[x] = ++cnt;
      update(m + 1, e, rc[x], g, v);
    }
  }
  void update(line g, int v) { update(rangel, ranger, 1, g, v); }

  pint query(lint s, lint e, int x, lint p) {
    if (s == e) return pint(f[x](p), t[x]);
    lint m = (s + e) / 2;
    if (p <= m)
      return min(pint(f[x](p), t[x]),
                 lc[x] ? query(s, m, lc[x], p) : pint(inf, 0));
    else
      return min(pint(f[x](p), t[x]),
                 rc[x] ? query(m + 1, e, rc[x], p) : pint(inf, 0));
  }
  pint query(lint p) { return query(rangel, ranger, 1, p); }
} t;

int N, M, K, bef[500004];
lint dp[500004];
vector<pint> p;

lint square(lint x) { return x * x; }
pint opt(lint C) {
  t.init();

  for (int i = 0; i < N; i++) {
    t.update(line(-4 * (p[i].x - 1),
                  2 * square(p[i].x - 1) + (i == 0 ? 0 : dp[i - 1])),
             i - 1);

    tie(dp[i], bef[i]) = t.query(p[i].y);
    dp[i] += 2 * square(p[i].y) + C;
    if (i + 1 < N and p[i + 1].x <= p[i].y) {
      dp[i] -= 2 * square(p[i].y - p[i + 1].x + 1);
    }
  }

  int cnt = 0;
  for (int i = N - 1; i >= 0; i = bef[i]) cnt++;

  return pint(dp[N - 1], cnt);
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  N = n;
  M = m;
  K = k;
  for (int i = 0; i < N; i++) p.emplace_back(min(r[i], c[i]), max(r[i], c[i]));

  sort(p.begin(), p.end(),
       [](pint x, pint y) { return x.x < y.x or (x.x == y.x and x.y > y.y); });

  vector<pint> realp;
  for (int i = 0, ymx = -1; i < N; i++)
    if (ymx < p[i].y) {
      realp.push_back(p[i]);
      ymx = p[i].y;
    }

  swap(p, realp);
  N = p.size();

  lint s = -1, e = 2e12 + 7;

  while (s + 1 < e) {
    lint m = (s + e) / 2;
    if (opt(m).y <= K)
      e = m;
    else
      s = m;
  }

  pint ans = opt(e);

  return (ans.x - K * e) / 2;
}

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