제출 #1223185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223185		fermat	Cake 3 (JOI19_cake3)	C++20	100 / 100	1253 ms	147988 KiB

cake3

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 2e5 + 5;

int n, m, sz = 1, root[N];

pair <int, int> a[N];

struct tree{
 int l, r, cnt;
 long long sum;
};

tree t[N * 32];

long long ans = -1e18;

void update (int ov, int nv, int pos, int tl = 1, int tr = 1e9){

 if (tl == tr)
  t[nv].cnt = t[ov].cnt + 1,
  t[nv].sum = t[ov].sum + tl;
  
 else{
  int tm = (tl + tr) >> 1;
  
  if (pos <= tm){
   t[nv].l = ++sz;
   t[nv].r = t[ov].r;
   update( t[ov].l, t[nv].l, pos, tl, tm );
  }
  else{
   t[nv].r = ++sz;
   t[nv].l = t[ov].l;
   update( t[ov].r, t[nv].r, pos, tm + 1, tr );
  }
  t[nv].cnt = t[ t[nv].l ].cnt + t[ t[nv].r ].cnt;
  t[nv].sum = t[ t[nv].l ].sum + t[ t[nv].r ].sum;
 }
}
long long get (int ov, int nv, int k = m, int tl = 1, int tr = 1e9)
{
 if (tl == tr)
  return k * 1ll * tl;
 
 int tm = (tl + tr) >> 1;
 
 if (k > t[ t[nv].r ].cnt - t[ t[ov].r ].cnt)
  return get(t[ov].l, t[nv].l, k - (t[ t[nv].r ].cnt - t[ t[ov].r ].cnt), tl, tm) + (t[ t[nv].r ].sum - t[ t[ov].r ].sum);

 return get(t[ov].r, t[nv].r, k, tm + 1, tr);
} 
void calc (int l, int r, int opl, int opr)
{
 if (l > r) return;
 
 int md = (l + r) >> 1;
 
 int opt = opl;
 long long res = -1e18;
 
 for (int i = opl; i <= min(opr, md - m + 1); i++){
  
  long long sup = get(root[i - 1], root[md]);
  if ( sup - (a[md].fr - a[i].fr) * 2 > res){
   res = sup - (a[md].fr - a[i].fr) * 2;
   opt = i;
  }
 }
 ans = max(ans, res);
 
 calc(l, md - 1, opl, opt);
 calc(md + 1, r, opt, opr);
}

main(){
 cin >> n >> m;
 
 for (int i = 1; i <= n; i++){
  scanf("%d%d", &a[i].sc, &a[i].fr);
 }
 sort(a + 1, a + n + 1);
 
 for (int i = 1; i <= n; i++){
  root[i] = ++sz;
  update(root[i - 1], root[i], a[i].sc);
 } 
 calc( 1, n, 1, n );
 
 cout << ans << endl;
}

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

cake3.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main(){
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d%d", &a[i].sc, &a[i].fr);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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