Submission #681801

#	Time	Username	Problem	Language	Result	Execution time	Memory
681801		cadmiumsky	Aliens (IOI16_aliens)	C++14	100 / 100	1125 ms	70664 KiB

aliens

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

#warning fa cu ll
using namespace std;

using ll = long long;

#define int ll
#define sz(x) (int)(x).size()

const int nmax = 1e6 + 5;

struct line {
  int chosen = 0;
  ll dp = 0, b = (ll)nmax * nmax;
  line(int x = 0, ll y = (ll)nmax * nmax, ll z = (ll)nmax * nmax): chosen(x), dp(y), b(z) {;}
  ll operator()(const ll& x) const { return b * x + dp; }
  bool operator()(const line& form, const line& cand) const {
    return (dp - form.dp) * (cand.b - b) > (dp - cand.dp) * (form.b - b) || ((dp - form.dp) * (cand.b - b) == (dp - cand.dp) * (form.b - b) && (b < cand.b || (b == cand.b && dp < cand.dp)));
  }
};

struct CHT {
  line cht[nmax];
  int ptr, lim;
  struct undo_info {
    line last;
    int ptrlast;
    int lstptr;
    int lstlim;
    undo_info(line a, int x, int y, int z): last(a), ptrlast(x), lstptr(y), lstlim(z) {;}
  };
  vector<undo_info> undost;
  int getT() { return sz(undost); }
  void push(line nv) {
    undost.emplace_back(line(), 0, ptr, lim);
    while(lim > 1 && nv(cht[lim - 2], cht[lim - 1])) lim--;
    
    undost.back().last = cht[lim];
    undost.back().ptrlast = lim;
    
    cht[lim++] = nv;
    ptr = min(lim - 1, ptr);
  }
  void undo() {
    cht[undost.back().ptrlast] = undost.back().last;
    ptr = undost.back().lstptr;
    lim = undost.back().lstlim;
    undost.pop_back();
    //cerr << "? " << lim << '\n';
  }
  void undo(int T) {
    assert(T >= 0);
    while(getT() > T)
      undo();
  }
  line query(int x) { // blea??
    while(ptr < lim - 1 && cht[ptr + 1](x) < cht[ptr](x))
      ptr++;
    //cerr << x << ' ' << cht[ptr](x) << '\t';
    //for(int i = 0; i < lim; i++)
      //cerr << cht[i](x) << ' ';
    //cerr << '\n';
    return cht[ptr];
  }
  void init() {
    undost.clear();
    ptr = 0;
    lim = 1;
    cht[0] = line(0, 0, 0);
    undost.reserve(nmax);
  }
} cht;

ll p2(ll x) { return x * x; }

line calculate(const vector<int>& height, ll C) {
  cht.init();
  
  vector<ll> dp(sz(height));
  vector<int> chosen(sz(height)), altern = height, st;
  st.reserve(sz(height));
  st.emplace_back(0);
  
  
  for(int i = 1; i < sz(altern); i++) altern[i] -= i;
  
  //for(auto x : height)
    //cerr << x << ' ';
  //cerr << '\n';
  //for(auto x : altern)
    //cerr << x << ' ';
  //cerr << '\n';
  
  for(int i = 1; i < sz(height); i++) {
    while(altern[st.back()] < altern[i])
      (height[st.back()]? cht.undo() : void()),
      st.pop_back();
    if(height[i] != 0) {
      cht.push(line(chosen[st.back()], (ll)dp[st.back()] - p2(st.back()) - (ll)2 * st.back() * (altern[i]), (ll)2 * (altern[i])));
      auto best = cht.query(i);
      dp[i] = best(i) + p2(i) + C;
      chosen[i] = best.chosen + 1;      
    }
    else {
      chosen[i] = chosen[i - 1], dp[i] = dp[i - 1];
    }
    //cerr << dp[i] << ' ';
    st.push_back(i);
    //for(auto x : st) cerr << x << ' ';
    //cerr << "\n---\n";
    //cerr << dp[i] << '\n';
  }
  //cerr << '\n';
  return line{chosen.back(), dp.back(), 0};
}

ll smenufromaliens(const vector<int>& height, int k) {
  ll lim = -1;
  for(ll i = (1LL << 40); i > 0; i >>= 1) {
    if(calculate(height, lim + i).chosen > k)
      lim += i;
  }
  return lim + 1;
}

ll take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) {
  if(n == 0) return 0;
  vector<int> height(m + 1);
  height[0] = m + 5;
  for(int i = 0; i < n; i++)
    r[i]++,
    c[i]++,
    height[max(r[i], c[i])] = max(height[max(r[i], c[i])], (ll)abs(r[i] - c[i]) + 1);
  while(height.back() == 0)
    height.pop_back();
  int lim = smenufromaliens(height, k);
  //int lim = 0;
  
  auto lol = calculate(height, lim);
  //cerr << lim << ' ' << lol.dp << ' ' << lol.chosen << ' ' << k << '\n';
  return (ll)lol.dp - (ll)lim * k;
}
#undef int

Compilation message (stderr)

aliens.cpp:4:2: warning: #warning fa cu ll [-Wcpp]
    4 | #warning fa cu ll
      |  ^~~~~~~

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