Submission #46923

#	Time	Username	Problem	Language	Result	Execution time	Memory
46923		tincamatei	Aliens (IOI16_aliens)	C++14	4 / 100	10 ms	940 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;

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

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

void addbatch(Dreapta x) {
  while(top > 0 && scoate(x)) {
    --top;
    batch.pop_back();
  }
  ++top;
  batch.push_back(x);
}

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

long long dp[1+MAX_N];

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

bool check(int cost, int n, int k) {
  batch.clear();
  top = 0;
  dp[0] = 0;
  addbatch({(long long)sqr(v[1].l) - 2 * v[1].l,
            -2 * v[1].l,
            0});
  
  for(int i = 1; i <= n; ++i) {
    dp[i] = querybatch(v[i].r) + sqr(v[i].r + 1) + cost;
    addbatch({(long long)sqr(v[i + 1].l) - 2 * v[i+1].l - sqr(max(0, (v[i].r - v[i+1].l + 1))) + dp[i],
              -2 * v[i+1].l,
              batch[0].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;
  int 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 = m * m + 1;
  while(dr - st > 1) {
    int mid = (st + dr) / 2;
    if(check(mid, n, k))
      dr = mid;
    else
      st = mid;
  }
  check(dr, n, k);
  return dp[n] - batch[top - 1].photos * dr;
}

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