제출 #1127402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127402		VinhLuu	Cake 3 (JOI19_cake3)	C++20	100 / 100	2058 ms	19804 KiB

cake3

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

#define lpv

#ifndef lpv
#include "AC.h"
#endif // lpv

#define int long long

const int N = 1e6 + 5;
const int oo = -1e16;

int n, m, a[N], b[N], _v[N], _c[N], idx[N], be[N], sz;
pair<int,int> p[N];
vector<int> rrh;

int st[N << 2], T[N << 2];

void update(int i,int l,int r,int u,int x) {
  if(l > r || r < u || u < l) return;
  if(l == r) {
    st[i] += x;
    T[i] += x * rrh[l - 1];
    return;
  }
  int mid = (l + r) / 2;
  update(i << 1, l, mid, u, x);
  update(i << 1|1, mid + 1, r, u, x);
  st[i] = st[i << 1] + st[i << 1|1];
  T[i] = T[i << 1] + T[i << 1|1];
}

int now = 0;

int get(int i,int l,int r,int num) {
  if(!num) return 0;
  if(num >= st[i]) return T[i];
//  cerr << l << " " << r << " t\n";
//  now++;
//  if(now > 20) exit(0);
  if(l == r) {
    return min(num, st[i]) * (T[i] / max(1ll, st[i]));
  }
  int mid = (l + r) / 2;
  if(st[i << 1|1] <= num) {
    return get(i << 1, l, mid, num - st[i << 1|1]) + T[i << 1|1];
  } else return get(i << 1|1, mid + 1, r, num);
}

int _left, _right;

ll ans = oo;

void solve (int l,int r,int pl,int pr) {
  if(l > r) return;
  int mid = (l + r) / 2;
//  cerr << mid << " " << l << " " << r << " start\n";
  while(_right < mid) update(1, 1, sz, be[++_right], 1);
  while(_left > min(mid, pr)) update(1, 1, sz, be[--_left], 1);
  while(_right > mid) update(1, 1, sz, be[_right--], -1);
  while(_left < min(mid, pr)) update(1, 1, sz, be[_left++], -1);
  ll tmp = oo, pos = pl;
  for(int i = min(mid, pr); i >= pl; i --) {
//       cerr << i << " ooo\n";
    while(_left > i) update(1, 1, sz, be[--_left], 1);
//    cerr << i << " p\n";
    ll val = get(1, 1, sz, m) - 2 * (a[mid] - a[i]);
    if(mid - i + 1 < m) val = oo;
//    cerr << mid << " " << i << " " << _left << " " << _right << " " << get(1, 1, sz, m) << " " <<  a[mid] << " " <<  a[i] << " " <<  val << " e\n";
    if(val > tmp) {
      tmp = val;
      pos = i;
    }
  }
  ans = max(ans, tmp);
  solve(l, mid - 1, pl, pos);
  solve(mid + 1, r, pos, pr);
}

#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> m;
  for(int i = 1; i <= n; i ++) {
    cin >> _v[i] >> _c[i];
    idx[i] = i;
  }

  sort(idx + 1, idx + n + 1, [&](int x,int y){return _c[x] < _c[y];});

  for(int i = 1; i <= n; i ++) {
    a[i] = _c[idx[i]];
    b[i] = _v[idx[i]];
    rrh.push_back(b[i]);
  }

  sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());

  sz = (int)rrh.size();

  for(int i = 1; i <= n; i ++) be[i] = lower_bound(all(rrh), b[i]) - rrh.begin() + 1;

  _left = 1, _right = 1; update(1, 1, sz, be[1], 1);

  solve(m, n, 1, n);

  cout << ans << "\n";

}
#endif // lpv

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'int main()':
cake3.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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