oj.uz

Submission #410349

# Submission time Handle Problem Language Result Execution time Memory
410349 2021-05-22T14:37:03 Z NurstanDuisengaliev 3D Histogram (COCI20_histogram) C++14
110 / 110
 491 ms 39508 KB 
// Nurstan Duisengaliev(REALBOY)
// Respa Gold_2022
// IZHO GOLD_2022
// IOI_2022 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3")*/                   
      
#include <bits/stdc++.h>
 
#define ll long long
#define all(x) x.begin(), x.end()
#define in insert
#define mp make_pair
#define F first
#define S second
#define ppf pop_front
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair <ll, ll>
#define boost() ios_base::sync_with_stdio(0), cin.tie(0)
#define sz(x) (int)x.size()
#define int ll
using namespace std;
 
const int N = (int)2e5 + 123;
const int mod = (int)1e9 + 7;
const ll INF = (ll)1e18 + 1;
int n, a[N], b[N];
ll ans = 0;
void Case1 (int l, int mid, int r) {
	int pos = mid, minia = mod, minib = mod;
	for (int i = mid; i >= l; i --) {
		minia = min (minia, a[i]);
		minib = min (minib, b[i]);
		while (pos < r && a[pos + 1] >= minia && b[pos + 1] >= minib) pos ++;
		ans = max (ans, minia * 1ll * minib * 1ll * (pos - i + 1));	
	}
}
vector <pii> d[N * 4];
vector <pii> line;
int ok[N * 4];
int intercept (pii a, pii b, pii c, pii d) {
	return (b.S - a.S) * (c.F - d.F) - (d.S - c.S) * (a.F - b.F);
}
void Build (int v, int l, int r) {
	if (l == r) {
		ok[v] = 0;
		d[v].pb (line[l]);
		return;
	}
	int mid = l + r >> 1;
	Build (v * 2, l, mid);
	Build (v * 2 + 1, mid + 1, r);	
	d[v] = d[v * 2];
	for (auto it : d[v * 2 + 1]) {
		while (sz (d[v]) >= 2 && intercept (d[v][sz (d[v]) - 1], it, d[v][sz (d[v]) - 1], d[v][sz (d[v]) - 2]) <= 0) {
			d[v].ppb ();
		}
		d[v].pb (it);
	}
	ok[v] = sz (d[v]) - 1;
}
void Build_CHT (int l, int mid, int r) {
	line.clear ();    
    int minib = mod;
	for (int i = mid + 1; i <= r; i ++) {
		minib = min (minib, b[i]);
		line.pb (mp (minib, minib * i));  
	}	
	for (int i = 1; i <= sz (line) * 4; i ++) d[i].clear ();
	Build (1, 0, sz (line) - 1);
}
ll Val (ll x, pii k) {
	return x * k.F + k.S;	
}
ll Get (int v, int l, int r, int nl, int nr, int x) {
	if (nl > r || l > nr) return 0ll;
	if (nl <= l && r <= nr) {
		while (ok[v] - 1 >= 0 && Val (x, d[v][ok[v] - 1]) >= Val (x, d[v][ok[v]])) ok[v] --;
		return Val (x, d[v][ok[v]]);			
	}
	int mid = l + r >> 1;
	return max (Get (v * 2, l, mid, nl, nr, x), Get (v * 2 + 1, mid + 1, r, nl, nr, x));
}
void Case2 (int l, int mid, int r) {
	int minia = mod, minib = mod, minio = mod, sl = mid, sr = mid;
	vector <pii> interval;
	for (int i = mid; i >= l; i --) {
		minia = min (minia, a[i]);
		minib = min (minib, b[i]);
		while (sr < r && a[sr + 1] >= minia) sr ++;
		while (sl <= r && minio > minib) {
			sl ++;
			minio = min (minio, b[sl]);
		}
		// sl....sr
		interval.pb (mp (sl - mid - 1, sr - mid - 1));
	}	
	Build_CHT (l, mid, r);
	minia = mod;
	for (int i = mid; i >= l; i --) {
		minia = min (minia, a[i]);
		// interval[mid - i]
		int L = interval[mid - i].F, R = interval[mid - i].S;
		if (L >= 0 &&  L <= R) {
			ans = max (ans, minia * 1ll * Get (1, 0, sz (line) - 1, L, R, 1 - i));
		}
	}
}
void calc (int l, int r, int t) {
	if (l > r) return;
	if (l == r) {
		ans = max (ans, a[l] * 1ll * b[l]);
		return;
	}
	int mid = (l + r - t) / 2;
	Case1 (l, mid, r);
	Case2 (l, mid, r);
	calc (l, mid, t);
	calc (mid + 1, r, t);	
} 
ll solve () {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i] >> b[i];
	}		      
	ans = 0;
	calc (1, n, 0);
	reverse (a + 1, a + n + 1);
	reverse (b + 1, b + n + 1);
	calc (1, n, 1);
	return ans; 
}   	
 
main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	boost ();
	cout << solve ();
	return 0;	                                    
}

Compilation message

histogram.cpp: In function 'void Build(long long int, long long int, long long int)':
histogram.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int mid = l + r >> 1;
      |            ~~^~~
histogram.cpp: In function 'long long int Get(long long int, long long int, long long int, long long int, long long int, long long int)':
histogram.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |  int mid = l + r >> 1;
      |            ~~^~~
histogram.cpp: At global scope:
histogram.cpp:139:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  139 | main () {
      | ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19276 KB Output is correct
2 Correct 14 ms 19228 KB Output is correct
3 Correct 14 ms 19224 KB Output is correct
4 Correct 13 ms 19276 KB Output is correct
5 Correct 16 ms 19312 KB Output is correct
6 Correct 12 ms 19312 KB Output is correct
7 Correct 16 ms 19276 KB Output is correct
8 Correct 16 ms 19316 KB Output is correct
9 Correct 12 ms 19276 KB Output is correct
10 Correct 16 ms 19276 KB Output is correct
11 Correct 9 ms 19152 KB Output is correct
12 Correct 17 ms 19276 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19276 KB Output is correct
2 Correct 14 ms 19228 KB Output is correct
3 Correct 14 ms 19224 KB Output is correct
4 Correct 13 ms 19276 KB Output is correct
5 Correct 16 ms 19312 KB Output is correct
6 Correct 12 ms 19312 KB Output is correct
7 Correct 16 ms 19276 KB Output is correct
8 Correct 16 ms 19316 KB Output is correct
9 Correct 12 ms 19276 KB Output is correct
10 Correct 16 ms 19276 KB Output is correct
11 Correct 9 ms 19152 KB Output is correct
12 Correct 17 ms 19276 KB Output is correct
13 Correct 421 ms 37276 KB Output is correct
14 Correct 333 ms 37624 KB Output is correct
15 Correct 451 ms 37440 KB Output is correct
16 Correct 439 ms 37372 KB Output is correct
17 Correct 441 ms 39508 KB Output is correct
18 Correct 391 ms 39500 KB Output is correct
19 Correct 382 ms 38948 KB Output is correct
20 Correct 383 ms 39384 KB Output is correct
21 Correct 473 ms 37536 KB Output is correct
22 Correct 491 ms 39460 KB Output is correct
23 Correct 42 ms 21020 KB Output is correct
24 Correct 427 ms 37300 KB Output is correct