Submission #233245

#	Time	Username	Problem	Language	Result	Execution time	Memory
233245		AlexLuchianov	Cake 3 (JOI19_cake3)	C++14	100 / 100	2836 ms	30312 KiB

cake3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <map>
#include <unordered_map>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
ll const inf = 1000000000000000000;

pair<int,int> v[5 + nmax];

unordered_map<int,int> code;
int decode[1 + nmax];

void normalize(int n){
  vector<int> temp;
  for(int i = 1;i <= n; i++)
    temp.push_back(v[i].second);
  sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  for(int i = 0; i < temp.size(); i++) {
    code[temp[i]] = 1 + i;
    decode[i + 1] = temp[i];
  }
  for(int i = 1;i <= n; i++)
    v[i].second = code[v[i].second];
}

class SegmentTree{
private:
  vector<pair<int, ll>> aint;
  pair<int, ll> _add(pair<int, ll> f1, pair<int,ll> f2){
    return {f1.first + f2.first, f1.second + f2.second};
  }
public:
  SegmentTree(int n){
    aint.resize(1 + 4 * n);
  }

  void computenode(int node, int from, int to){
    aint[node] = _add(aint[node * 2], aint[node * 2 + 1]);
  }

  void update(int node, int from, int to, int x, pair<int, ll> val){
    aint[node] = _add(aint[node], val);
    if(from < to){
      int mid = (from + to) / 2;
      if(x <= mid)
        update(node * 2, from, mid, x, val);
      else
        update(node * 2 + 1, mid + 1, to, x, val);
    }
  }

  ll query(int node, int from, int to, int k){
    if(aint[node].first < k)
      return -inf;
    if(from < to){
      int mid = (from + to) / 2;
      if(k <= aint[node * 2 + 1].first)
        return query(node * 2 + 1, mid + 1, to, k);
      else
        return query(node * 2, from, mid , k - aint[node * 2 + 1].first) + aint[node * 2 + 1].second;
    } else
      return 1LL * decode[from] * k;
  }

  int _size(){
    return aint[1].first;
  }
};

int n, k;
ll result = -inf;

void _insert(SegmentTree &aint, int val){
  aint.update(1, 1, n, val, {1, decode[val]});
}
void _erase(SegmentTree &aint, int val){
  aint.update(1, 1, n, val, {-1, -decode[val]});
}

ll dp[1 + nmax], sol[1 + nmax];

ll extract(int start, int stop, SegmentTree &aint){
  return aint.query(1, 1, n, k) - (v[stop].first - v[start].first) * 2;
}

void eval(int pos, int x, int y, SegmentTree &aint){
  dp[pos] = -inf;
  sol[pos] = n;

  x = max(pos, x);
  for(int i = x; i <= y; i++){
    _insert(aint, v[i].second);
    ll result = extract(pos, i, aint);
    if(dp[pos] < result){
      dp[pos] = result;
      sol[pos] = i;
    }
  }

  for(int i = x; i <= y; i++)
    _erase(aint, v[i].second);
}

void divide(int from, int to, int x, int y, SegmentTree &aint){
  if(to < from)
    return ;
  int mid = (from + to) / 2;

  for(int i = mid; i <= min(x - 1, to); i++)
    _insert(aint, v[i].second);
  eval(mid, x, y, aint);
  divide(from, mid - 1, x, sol[mid], aint);
  for(int i = mid; i <= min(to, x - 1); i++)
    _erase(aint, v[i].second);

  for(int i = max(to + 1, x); i < sol[mid]; i++)
    _insert(aint, v[i].second);
  divide(mid + 1, to, sol[mid], y, aint);
  for(int i = max(to + 1, x); i < sol[mid]; i++)
    _erase(aint, v[i].second);
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> k;
  for(int i = 1;i <= n; i++) {
    cin >> v[i].second >> v[i].first;
  }

  sort(v + 1, v + n + 1);
  normalize(n);
  SegmentTree aint(n);
  divide(1, n, 1, n, aint);
  ll result = -inf;
  for(int i = 1;i <= n; i++)
    result = max(result, dp[i]);
  cout << result;
  return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void normalize(int)':
cake3.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++) {
                  ~~^~~~~~~~~~~~~

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