Submission #476321

#	Time	Username	Problem	Language	Result	Execution time	Memory
476321		Mackerel_Pike	3D Histogram (COCI20_histogram)	C++14	110 / 110	148 ms	3404 KiB

histogram

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;

int n;
int a[maxn], b[maxn], f[maxn], g[maxn];
long long ans;
bool DEBUG;

inline void calc1(int l, int r, int ql, int qr){
  if(l > r)
    return;
  int md = l + r >> 1, pos = -1;
  long long ret = 0;
  for(int i = ql; i <= qr; ++i){
    long long res = 1ll * (i - md + 1) * min(f[md], f[i]) * min(g[md], g[i]);
    if(!~pos || res >= ret)
      ret = res, pos = i;
  }
  ans = max(ans, ret);
  calc1(l, md - 1, ql, pos);
  calc1(md + 1, r, pos, qr);
  return;
}

inline void calc2(int l, int r, int ql, int qr){
  if(l > r)
    return;
  int md = l + r >> 1, pos = -1;
  long long ret = 0;
  for(int i = ql; i <= qr; ++i){
    long long res = 1ll * (i - md + 1) * min(f[md], f[i]) * min(g[md], g[i]);
    if(!~pos || res >= ret)
      ret = res, pos = i;
  }
  ans = max(ans, ret);
  calc2(l, md - 1, pos, qr);
  calc2(md + 1, r, ql, pos);
  return;
}

inline void solve(int l, int r){
  if(l == r){
    ans = max(ans, 1ll * a[l] * b[l]);
    return;
  }
  int md = l + r >> 1;
  for(int i = md; i >= l; --i){
    f[i] = min(i == md ? 0x3f3f3f3f : f[i + 1], a[i]);
    g[i] = min(i == md ? 0x3f3f3f3f : g[i + 1], b[i]);
  }
  for(int i = md + 1; i <= r; ++i){
    f[i] = min(i == md + 1 ? 0x3f3f3f3f : f[i - 1], a[i]);
    g[i] = min(i == md + 1 ? 0x3f3f3f3f : g[i - 1], b[i]);
  }
  calc1(l, md, md + 1, r);
  calc2(l, md, md + 1, r);
  solve(l, md), solve(md + 1, r);
  return;
}

int main(){
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d%d", a + i, b + i);

  solve(0, n - 1);

  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

histogram.cpp: In function 'void calc1(int, int, int, int)':
histogram.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |   int md = l + r >> 1, pos = -1;
      |            ~~^~~
histogram.cpp: In function 'void calc2(int, int, int, int)':
histogram.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   int md = l + r >> 1, pos = -1;
      |            ~~^~~
histogram.cpp: In function 'void solve(int, int)':
histogram.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int md = l + r >> 1;
      |            ~~^~~
histogram.cpp: In function 'int main()':
histogram.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
histogram.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d%d", a + i, b + i);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 90 / 90