Submission #46924

#	Time	Username	Problem	Language	Result	Execution time	Memory
46924		tincamatei	Aliens (IOI16_aliens)	C++14	100 / 100	482 ms	68592 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;

struct Segment {
  int l, r;
} v[1+MAX_N];

struct cmp {
  bool operator() (Segment a, Segment b) {
    return a.l < b.l;
  }
};

bool cmp2(Segment a, Segment b) {
  return a.r < b.r || (a.r == b.r && a.l > b.l);
}

set<Segment, cmp> xd;
set<Segment, cmp>::iterator it;

void unify(int &n) {
  std::sort(v, v + n, cmp2);
  for(int i = 0; i < n; ++i) {
    it = xd.lower_bound({v[i].l, 0});
    while(it != xd.end())
      it = xd.erase(it);
    xd.insert(v[i]);
  }
  
  n = 0;
  for(it = xd.begin(); it != xd.end(); it++)
    v[++n] = *it;
}

struct Dreapta {
  long long yinter, slope;
  int photos;
};

deque<Dreapta> batch;
int top;

long double intersect(Dreapta a, Dreapta b) {
  return ((double)a.yinter - b.yinter) / (b.slope - a.slope);
}

bool scoate(Dreapta a) {
  if(top >= 2 && intersect(batch[top - 2], batch[top - 1]) >= intersect(batch[top - 2], a))
    return true;
  return false;
}

int pnt;
void addbatch(Dreapta x) {
  while(top > 1 && scoate(x)) {
    --top;
    batch.pop_back();
  }
  ++top;
  if(pnt >= top)
    pnt = top - 1;
  batch.push_back(x);
}

long long querybatch(int x) {
  while(pnt < top - 1 && x >= intersect(batch[pnt], batch[pnt + 1])) {
    ++pnt;
  }
  return batch[pnt].yinter + batch[pnt].slope * x;
}

long long dp[1+MAX_N];

static inline long long sqr(long long x) {
  return x * x;
}

bool check(long long cost, int n, int k) {
  batch.clear();
  top = 0;
  dp[0] = 0;
  v[0].l = v[0].r = -1;
  addbatch({dp[0] + sqr(v[1].l - 1) - 0,
            -2 * v[1].l,
            0});
  
  for(int i = 1; i <= n; ++i) {
    dp[i] = querybatch(v[i].r) + sqr(v[i].r + 1) - 1 + cost;
    addbatch({ dp[i] + sqr(v[i + 1].l - 1) - sqr(max(0, v[i].r - v[i + 1].l + 1)),
               -2 * v[i+1].l,
               batch[pnt].photos + 1});
  }
  return batch[top - 1].photos <= k;
}

long long take_photos(int n, int m, int k, vector<int> _l, vector<int> _r) {
  int a, b;
  long long st, dr;
  for(int i = 0; i < n; ++i) {
    a = _l[i];
    b = _r[i];
    v[i].l = min(a, b);
    v[i].r = max(a, b);
  }
  
  unify(n);
  st = 0;
  dr = (long long)m * m + 1;
  while(dr - st > 1) {
    long long mid = (st + dr) / 2;
    if(check(mid, n, k))
      dr = mid;
    else
      st = mid;
  }
  check(st, n, k);
  if(k > n)
    k = n;
  return dp[n] - st * k;
}

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