Submission #1050867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050867		_rain_	3D Histogram (COCI20_histogram)	C++14	0 / 110	1 ms	6492 KiB

histogram

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

template<class T1 , class T2>
	bool maximize(T1& a , T2 b)
	{
		if (a < b) return a = b , true;
		return false;
	}
template<class T1 , class T2>
	bool minimize(T1& a , T2 b)
	{
		if (a > b) return a = b , true;
		return false;
	}

const int maxn = 2e5;

//... CONVEXHULL
namespace ConvexHull
{
		struct Line
		{
			i64 a ;
			i64 b;
			Line(i64 a , i64 b) : a(a) , b(b) {};
		};
		struct Hull
		{
			Line X ;
			long double intersec;
		};
		class Convexhull
		{
			public:
				vector<Hull> line;

				long double getintersec(Line x , Line y)
				{
					return (long double)(y.b - x.b) / (x.a - y.a);
				}
				i64 f(Line a , i64 x)
				{
					return a.a * x + a.b;
				}

				void addline(Line x)
				{
					int n = line.size();
					while (n > 1 && getintersec(line[n - 2].X , line[n - 1].X) >= getintersec(line[n - 2].X , x))
						{
							--n;
							line.pop_back();
						}
					if (line.empty()) line.push_back({x , LLONG_MIN});
						else line.push_back({x , getintersec(x , line[n - 1].X)});
					return;
				}
				i64 find(i64 val)
				{
					int l = 0 , r = line.size()-1 , pos = 0;
					while (l<=r)
					{
						int m = l + r >> 1;
						if (line[m].intersec <= val)
							pos = m , l = m + 1;
						else r = m - 1;
					}
					return f(line[pos].X , val);
				}
				void add(i64 a , i64 b)
				{
					addline(Line{a,b});
					return;
				}
		};
}
using namespace ConvexHull;

const i64 INF = 1e18 + 7;
int n;
i64 a[maxn+2],b[maxn+2];
i64 mnA[maxn+2][2] , mnB[maxn+2][2];

void build_LEFT(int l , int r)
{
	mnA[r+1][0] = mnB[r+1][0] = INF;
	for (int i = r; i >= l; --i)
	{
		mnA[i][0]=min(mnA[i+1][0],a[i]);
		mnB[i][0]=min(mnB[i+1][0],b[i]);
	}
	return;
}
void build_RIGHT(int l , int r)
{
	mnA[l-1][1] = mnB[l-1][1] = INF;
	for (int i = l; i <= r; ++i)
	{
		mnA[i][1]=min(mnA[i-1][1],a[i]);
		mnB[i][1]=min(mnA[i-1][1],b[i]);
	}
	return; 
}

i64 case1(int l , int m , int r) // LEFT IN MINA , RIGHT IN MINB
{
	Convexhull bag;
	i64 res = 0;
	int j = m;
	for (int i = m; i >= l; --i)
	{
		bool ok = false;
		while (j <= r && mnA[i][0] <= mnA[j][1] && mnB[i][0] >= mnB[j][1])
		{
			bag.add(-mnB[j][1] , mnB[j][1] * (j + 1));
			++j;
			ok = true;
		}
		if (bag.line.size() && ok)
		{
			res = max({
				res , mnA[i][0] * bag.find(i)
			});
			// cout << '(' << i << ',' << j - 1 << " || VALUE ARE : " << mnA[i][0] << ',' << mnB[j - 1][1] << ',' <<mnA[i][0] * bag.find(i) << ')' << '\n';
			// cout << '(' << i << ',' << j - 1 << " || VALUE ARE : " << mnA[i][0] *bag.line[bag.find(i)].X.a * i<<','<<bag.line[bag.find(i)].X.b << ')' << '\n';
		}
	}
	return res;
}
i64 case2(int l , int m , int r) // LEFT IS MINB , RIGHT IS MINA
{
	Convexhull bag;
	i64 res = 0;
	int j = m;
	for (int i = m; i >= l; --i)
	{
		bool ok = false;
		while (j <= r && mnB[i][0] <= mnB[j][1] && mnA[i][0] >= mnA[j][1])
		{
			ok = true;
			bag.add(-mnA[j][1] , mnA[j][1] * (j + 1));
			++j;
		}
		if (bag.line.size() && ok)
		{
			res = max({
				res , mnB[i][0] * bag.find(i)
			});
			// cout << '(' << i << ',' << j - 1 << " || VALUE ARE : " << mnB[i][0] << ',' << mnA[j - 1][1] << ',' << mnB[i][0]*bag.find(i) << ')' << '\n';
		}
	}
	return res;
}

i64 solve(int l , int r)
{
	if (l > r) return 0;
	if (l==r) return a[l] * b[r];
	int m = l + r >> 1;	
	build_LEFT(l,m);
	build_RIGHT(m,r);

	// cout << "TURN\n";
	// cout << l << ' ' << m << ' ' << r << '\n';
	i64 res = 0;
		// cout << "CASE1\n";
	res = max(res , case1(l,m,r));
		// cout << "CASE2\n";
	res = max(res , case2(l,m,r));
		// cout<<'\n';
		// cout << "END CASE\n";
	res = max({res , solve(l,m) , solve(m+1,r)});
	return res;
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	#define name "main"
	if (fopen(name".inp","r"))
	{
		(void)freopen(name".inp","r",stdin);
		(void)freopen(name".out","w",stdout);
	}
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
	// for (int i = 1; i <= n; ++i) cout << a[i] << ' ' << b[i] << '\n';
	cout << solve(1,n);
}

Compilation message (stderr)

histogram.cpp: In member function 'i64 ConvexHull::Convexhull::find(i64)':
histogram.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |       int m = l + r >> 1;
      |               ~~^~~
histogram.cpp: In function 'i64 solve(int, int)':
histogram.cpp:161:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |  int m = l + r >> 1;
      |          ~~^~~
histogram.cpp: In function 'int main()':
histogram.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |   (void)freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |   (void)freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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