Submission #555924

#	Time	Username	Problem	Language	Result	Execution time	Memory
555924		MilosMilutinovic	Aliens (IOI16_aliens)	C++14	100 / 100	1051 ms	9472 KiB

aliens

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

using namespace std;

const int MAX = 1000005;

struct Line {
  long long k, n;
  int cnt;
  Line() {}
  Line(long long _k, long long _n, int _cnt) : k(_k), n(_n), cnt(_cnt) {}
  long long get(int x) {
    return k * (long long) x + n;
  }
};

int root, ls[4 * MAX], rs[4 * MAX], tsz;
Line st[4 * MAX];

void modify(int& node, int l, int r, Line k) {
  if (!node) {
    node = ++tsz;
    st[node] = k;
    return;
  }
  long long a = st[node].get(l);
  long long b = k.get(l);
  long long c = st[node].get(r);
  long long d = k.get(r);
  if (a >= b && c >= d) {
    return;
  }
  if (a <= b && c <= d) {
    st[node] = k;
    return;
  }
  int mid = l + r >> 1;
  if (a < b) {
    swap(st[node], k);
  }
  if (st[node].get(mid) > k.get(mid)) {
    modify(rs[node], mid + 1, r, k);
  } else {
    swap(st[node], k);
    modify(ls[node], l, mid, k);
  }
}

pair<long long, int> query(int node, int l, int r, int i) {
  if (!node) {
    return make_pair((long long) -1e18, -1e9);
  }
  if (l == r) {
    return make_pair(st[node].get(i), st[node].cnt);
  }
  auto val = make_pair(st[node].get(i), st[node].cnt);
  int mid = l + r >> 1;
  if (i <= mid) {
    val = max(val, query(ls[node], l, mid, i));
  } else {
    val = max(val, query(rs[node], mid + 1, r, i));
  }
  return val;
}

void build() {
  for (int i = 1; i <= tsz; i++) {
    ls[i] = 0;
    rs[i] = 0;
  }
  root = 0;
  tsz = 0;
}

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]);
    }
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    if (r[i] != r[j]) {
      return r[i] < r[j];
    } else {
      return c[i] > c[j];
    }
  });
  vector<pair<int, int>> pts;
  int mx = -1;
  for (int id = 0; id < n; id++) {
    int i = order[id];
    if (c[i] <= mx) {
      continue;
    } else {
      mx = max(mx, c[i]);
      pts.emplace_back(r[i], c[i]);
    }
  }
  n = (int) pts.size();
  k = min(k, n);
  for (int i = 0; i < n; i++) {
    r[i] = pts[i].first;
    c[i] = pts[i].second;
  }
  vector<long long> w(n);
  for (int i = 1; i < n; i++) {
    long long d = c[i - 1] - r[i] + 1;
    if (d < 0) {
      continue;
    }
    w[i - 1] = d * d;
  }
  auto Solve = [&](long long cost) {
    build();
    vector<long long> dp(n);
    vector<int> cnt(n);
    for (int i = 0; i < n; i++) {
      long long ft = 0;
      int fc = 0;
      if (i > 0) {
        ft = dp[i - 1] - w[i - 1];
        fc = cnt[i - 1];
      }
      modify(root, 0, MAX, Line(2 * r[i], -(r[i] * 1LL * r[i] + ft), -fc));
      auto it = query(root, 0, MAX, c[i] + 1);
      long long cs = -it.first + (c[i] + 1) * 1LL * (c[i] + 1);
      dp[i] = cs + cost;
      cnt[i] = -it.second + 1;
    }
    return make_pair(dp[n - 1], cnt[n - 1]);
  };
  long long low = 0, high = m * 1LL * m, ans = 0;
  while (low <= high) {
    long long mid = (low + high) >> 1;
    auto cs = Solve(mid);
    if (cs.second <= k) {
      high = mid - 1;
      ans = mid;
    } else {
      low = mid + 1;
    }
  }
  return Solve(ans).first - ans * k;
}

Compilation message (stderr)

aliens.cpp: In function 'void modify(int&, int, int, Line)':
aliens.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~
aliens.cpp: In function 'std::pair<long long int, int> query(int, int, int, int)':
aliens.cpp:58:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |   int mid = l + r >> 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