oj.uz

답안 #445466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445466 2021-07-18T06:56:16 Z grt 3D Histogram (COCI20_histogram) C++17
110 / 110
 158 ms 15248 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
 
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
 
const int nax = 200 * 1000 + 10;
int n;
int a[nax], b[nax], f[nax], g[nax];

struct Point {
	ll x, y;
	int id;
};

Point lines[nax];
ll ans;
vector<Point>S1, S2;
int ptr, last;
 
ll intersect(Point&x, Point&y, Point&z) {
	return (z.x - x.x) * (y.y - x.y) - (y.x - x.x)*(z.y - x.y);
}
 
ll get_mx(vector<Point>&vec, int x) {
	if((int)vec.size() == 0) return -1;
	while((int)vec.size() >= 2 && (ll)vec.back().x * x + vec.back().y <= (ll)vec[(int)vec.size() - 2].x * x + vec[(int)vec.size() - 2].y) {
		vec.pop_back();
	}
	return (ll)vec.back().x * x + vec.back().y;
}
 
ll get_mx2(int x) {
	if((int)S2.size() == 0) return -1;
	while(ptr + 1 < (int)S2.size() && S2[ptr+1].x * x + S2[ptr+1].y >= S2[ptr].x * x + S2[ptr].y) {
		ptr++;
	}
	return S2[ptr].x * x + S2[ptr].y;
}

vi rem[nax];
 
void rec(int l, int r) {
	int mid = ((l + r) >> 1);
	if(l <= mid - 1) rec(l, mid - 1);
	if(mid + 1 <= r) rec(mid + 1, r);
	f[mid] = a[mid];
	g[mid] = b[mid];
	lines[mid] = {g[mid], (ll)g[mid] * mid, mid};
	for(int i = mid - 1; i >= l; --i) {
		f[i] = min(f[i + 1], a[i]);
		g[i] = min(g[i + 1], b[i]);
		lines[i] = {g[i], (ll)g[i] * (-i + 1), i};
	}
	for(int i = mid + 1; i <= r; ++i) {
		f[i] = min(f[i - 1], a[i]);
		g[i] = min(g[i - 1], b[i]);
		lines[i] = {g[i], (ll)g[i] * i, i};
	}
	int lp, rp, l2, r2;
	rp = r;
	for(lp = l; lp <= mid; ++lp) {
		while(rp >= mid && (f[lp] > f[rp] || g[lp] > g[rp])) {
			rp--;
		}
		if(rp >= mid) {
			ans = max(ans, (ll)f[lp] * g[lp] * (rp - lp + 1));
		}
	}
	lp = l;
	for(rp = r; rp >= mid; rp--) {
		while(lp <= mid && (f[rp] > f[lp] || g[rp] > g[lp])) {
			lp++;
		}
		if(lp <= mid) {
			ans = max(ans, (ll)f[rp] * g[rp] * (rp - lp + 1));
		}
	}
	// --------------------------
	rp = r;
	r2 = r;
	S1.clear(); S2.clear();
	last = r + 1;
	ptr = 0;
	S1.PB(lines[r]);
	for(int i = mid; i <= r; ++i) rem[i].clear();
	for(lp = l; lp <= mid; lp++) {
		while(r2 - 1 >= mid && (g[lp] >= g[r2 - 1])) {
			r2--;
			if((int)S1.size() >= 1 && S1.back().x == lines[r2].x) continue;
			while((int)S1.size() >= 2 && intersect(S1.back(), lines[r2], S1[(int)S1.size() - 2]) <= 0) {
				S1.pop_back();
			}
			S1.PB(lines[r2]);
			// add
		}
		while(rp >= mid && (f[lp] > f[rp])) {
			rp--;
			// erase
		}
		if(rp >= mid && g[lp] >= g[r2] && r2 <= rp) {
			// [r2, rp]
			while(S2.size() > 0 && S2.back().id >= rp + 1) {
				if(ptr > 0) ptr--;
				reverse(rem[S2.back().id].begin(), rem[S2.back().id].end());
				int id = S2.back().id;
				S2.pop_back();
				for(int x : rem[id]) {
					S2.PB(lines[x]);
				}
				// must add points
			}
			if((int)S1.size() > 0 && S1[0].id >= rp + 1) {
				int nxt = S1.back().id;
				while((int)S1.size() > 0) {
					S1.pop_back();
				}
				for(int i = nxt; i < last; ++i) {
					if((int)S2.size() >= 1 && S2.back().x == lines[i].x) continue;
					while((int)S2.size() >= 2 && intersect(S2.back(), lines[i], S2[(int)S2.size() - 2]) >= 0) {
						rem[i].PB(S2.back().id);
						S2.pop_back();
					}
					S2.PB(lines[i]);
				}
				last = nxt;
				ptr = 0;
			}
			while(S2.size() > 0 && S2.back().id >= rp + 1) {
				if(ptr > 0) ptr--;
				reverse(rem[S2.back().id].begin(), rem[S2.back().id].end());
				int id = S2.back().id;
				S2.pop_back();
				for(int x : rem[id]) {
					S2.PB(lines[x]);
				}
				// must add points
				
			}
			ll w1 = get_mx(S1, -lp + 1);
			ll w2 = get_mx2(-lp + 1);
			//cerr << lp << " " << r2 << " " << rp << " " << max(w1, w2) * f[lp] << "\n";
			ans = max(ans, max(w1,w2) * f[lp]);
		}
	}
	// ---------------------------
	lp = l;
	l2 = l;
	lines[mid] = {(ll)g[mid], (ll)g[mid] * (-mid + 1), mid};
	S1.clear(); S2.clear();
	S1.PB(lines[l]);
	ptr = 0;
	last = l - 1;
	for(int i = l; i <= mid; ++i) rem[i].clear();
	for(rp = r; rp >= mid; rp--) {
		while(l2 + 1 <= mid && (g[rp] >= g[l2 + 1])) {
			l2++;
			if((int)S1.size() >= 1 && S1.back().x == lines[l2].x) continue;
			while((int)S1.size() >= 2 && intersect(S1.back(), lines[l2], S1[(int)S1.size() - 2]) <= 0) {
				S1.pop_back();
			}
			S1.PB(lines[l2]);
			// add
		}
		while(lp <= mid && (f[rp] > f[lp])) {
			lp++;
		}
		if(lp <= mid && g[rp] >= g[l2] && lp <= l2) {
			// [r2, rp]
			// ans = max(ans, ask(lp, l2, rp) * f[rp]);
			while(S2.size() > 0 && S2.back().id <= lp - 1) {
				if(ptr > 0) ptr--;
				reverse(rem[S2.back().id].begin(), rem[S2.back().id].end());
				int id = S2.back().id;
				S2.pop_back();
				for(int x : rem[id]) {
					S2.PB(lines[x]);
				}
				// must add points
			}
			if((int)S1.size() > 0 && S1[0].id <= lp - 1) {
				int nxt = S1.back().id;
				while((int)S1.size() > 0) {
					S1.pop_back();
				}
				for(int i = nxt; i > last; --i) {
					if((int)S2.size() >= 1 && S2.back().x == lines[i].x) continue;
					while((int)S2.size() >= 2 && intersect(S2.back(), lines[i], S2[(int)S2.size() - 2]) >= 0) {
						rem[i].PB(S2.back().id);
						S2.pop_back();
					}
					S2.PB(lines[i]);
				}
				last = nxt;
				ptr = 0;
			}
			while(S2.size() > 0 && S2.back().id <= lp - 1) {
				if(ptr > 0) ptr--;
				reverse(rem[S2.back().id].begin(), rem[S2.back().id].end());
				int id = S2.back().id;
				S2.pop_back();
				for(int x : rem[id]) {
					S2.PB(lines[x]);
				}
				// must add points
			}
			ll w1 = get_mx(S1, rp);
			ll w2 = get_mx2(rp);
			//if(mid == 1) {
				//cerr << rp << ":\n";
				//for(auto x : S1) {
					//cerr << x.x << " " << x.y << " " << x.id << "\n";
				//}
				//cerr << "---\n";
				//for(auto x : S2) {
					//cerr << x.x << " " << x.y << " " << x.id << "\n";
				//}
				//cerr << "---\n";
			//}
			ans = max(ans, max(w1,w2) * f[rp]);
		}
	}
	
	
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
	}
	rec(0, n - 1);
	cout << ans;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5128 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 6 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5128 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 6 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 150 ms 13456 KB Output is correct
14 Correct 158 ms 15248 KB Output is correct
15 Correct 118 ms 13240 KB Output is correct
16 Correct 116 ms 13280 KB Output is correct
17 Correct 128 ms 14496 KB Output is correct
18 Correct 123 ms 14640 KB Output is correct
19 Correct 128 ms 14164 KB Output is correct
20 Correct 140 ms 15184 KB Output is correct
21 Correct 137 ms 13248 KB Output is correct
22 Correct 150 ms 14536 KB Output is correct
23 Correct 16 ms 5840 KB Output is correct
24 Correct 129 ms 12820 KB Output is correct