Submission #885639

#	Time	Username	Problem	Language	Result	Execution time	Memory
885639		peterandvoi	Cake 3 (JOI19_cake3)	C++17	100 / 100	449 ms	8988 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

#define db(...) " [" << #__VA_ARGS__ << " : " << (__VA_ARGS__) << "] "

const int N = 200005;
const int LOG = 17;

#define MASK(x) (1LL << (x))

template<class T>
struct fenwick_tree {
  T s[N];
  
  void update(int i, T x) {
    for (; i <= 200000; i += i & -i) {
      s[i] += x;
    }
  }
  
  T get(int i) {
    T res = 0;
    for (; i > 0; i -= i & -i) {
      res += s[i];
    }
    return res;
  }
  
  T get(int l, int r) {
    return get(r) - get(l - 1);
  }
  
  int lower_bound(T k) {
    int x = 0;
    for (int i = MASK(LOG); i; i >>= 1) {
      if (x + i <= 200000 && k >= s[x + i]) {
        x += i;
        k -= s[x];
      }
    }
    return x;
  }
};

struct T {
  int v, c;
  
  T() {};
  
  T(int v, int c): v(v), c(c) {};
  
  bool operator < (const T &oth) const {
    return c < oth.c;
  }
  
  void read() {
    cin >> v >> c;
  }
} a[N];

int n, m;

int k;
vector<int> values;

int val(int idx) {
  return values[k - idx]; 
}

int L = 1, R = 0;

fenwick_tree<long long> ft;
fenwick_tree<int> num;

long long get() {
  int cnt = m - 2;
  int pos = num.lower_bound(cnt - 1) + 1;
  long long res = ft.get(pos - 1);
  cnt -= num.get(pos - 1);
  res += 1LL * val(pos) * cnt;
  return res;
}

long long res = -1e18;

void add(int i) {
  if (i) {
    num.update(a[i].v, 1);
    ft.update(a[i].v, val(a[i].v));  
  }
}

void del(int i) {
  if (i) {
    num.update(a[i].v, -1);
    ft.update(a[i].v, -val(a[i].v));  
  }
}

void dnc(int l, int r, int optl, int optr) {
  if (l > r) {
    return;
  }
  int mid = l + r >> 1;
  while (L > mid + 1) add(--L);
  while (R < optr) add(++R);
  while (L < mid + 1) del(L++);
  while (R > optr) del(R--);
  pair<long long, int> best = {-1e18, -1};
  for (int i = optr; i >= max(mid + m - 1, optl); --i) {
    while (R > i - 1) del(R--);
    long long cost = -2LL * (a[i].c - a[mid].c);
    cost += val(a[i].v);
    cost += val(a[mid].v);
    cost += get();
    if (cost > best.first) {
      best.first = cost;
      best.second = i;
    }
  }
  assert(best.second != -1);
  res = max(res, best.first);
  dnc(l, mid - 1, optl, best.second);
  dnc(mid + 1, r, best.second, optr);
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    a[i].read();
    values.emplace_back(a[i].v);
  }
  sort(values.begin(), values.end());
  values.erase(unique(values.begin(), values.end()), values.end());
  k = values.size();
  for (int i = 1; i <= n; ++i) {
    a[i].v = lower_bound(values.begin(), values.end(), a[i].v) - values.begin() + 1;
    a[i].v = k - a[i].v + 1;
  }
  sort(a + 1, a + n + 1);
  dnc(1, n - m + 1, m, n);
  cout << res;
}

Compilation message (stderr)

cake3.cpp: In function 'void dnc(int, int, int, int)':
cake3.cpp:105:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |   int mid = l + r >> 1;
      |             ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76