Submission #1159694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159694		hmm789	3D Histogram (COCI20_histogram)	C++20	0 / 110	2 ms	832 KiB

histogram

#include <bits/stdc++.h>
using namespace std;
#define int long long 

struct node {
	int s, e, m, a, b, c, ab, bc, ac, abc, lza, lzb, lzc;
	node *l, *r;
	node(int _s, int _e) {
		s = _s, e = _e, m = (s+e)/2, a = b = c = ab = bc = ac = abc = lza = lzb = lzc = 0;
		if(s != e) {
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void prop() {
		if(lza) { // set
			a = lza;
			ab = lza * b;
			ac = lza * c;
			abc = lza * bc;
			if(s != e) {
				l->lza = lza;
				r->lza = lza;
			}
			lza = 0;
		}
		if(lzb) { // set
			b = lzb;
			ab = lzb * a;
			bc = lzb * c;
			abc = lzb * ac;
			if(s != e) {
				l->lzb = lzb;
				r->lzb = lzb;
			}
			lzb = 0;
		}
		if(lzc) { // add
			c += lzc;
			ac += lzc * a;
			bc += lzc * b;
			abc += lzc * ab;
			if(s != e) {
				l->lzc += lzc;
				r->lzc += lzc;
			}
			lzc = 0;
		}
	}
	void rseta(int x, int y, int val) {
		prop();
		if(x <= s && e <= y) {
			lza = val; return;
		} else if(x > m) r->rseta(x, y, val);
		else if(y <= m) l->rseta(x, y, val);
		else l->rseta(x, y, val), r->rseta(x, y, val);
		l->prop(); r->prop();
		a = max(l->a, r->a);
		b = max(l->b, r->b);
		c = max(l->c, r->c);
		ab = max(l->ab, r->ab);
		bc = max(l->bc, r->bc);
		ac = max(l->ac, r->ac);
		abc= max(l->abc, r->abc);
	}
	void rsetb(int x, int y, int val) {
		prop();
		if(x <= s && e <= y) {
			lzb = val; return;
		} else if(x > m) r->rsetb(x, y, val);
		else if(y <= m) l->rsetb(x, y, val);
		else l->rsetb(x, y, val), r->rsetb(x, y, val);
		l->prop(); r->prop();
		a = max(l->a, r->a);
		b = max(l->b, r->b);
		c = max(l->c, r->c);
		ab = max(l->ab, r->ab);
		bc = max(l->bc, r->bc);
		ac = max(l->ac, r->ac);
		abc= max(l->abc, r->abc);
	}
	void raddc(int x, int y, int val) {
		prop();
		if(x <= s && e <= y) {
			lzc += val; return;
		} else if(x > m) r->raddc(x, y, val);
		else if(y <= m) l->raddc(x, y, val);
		else l->raddc(x, y, val), r->raddc(x, y, val);
		l->prop(); r->prop();
		a = max(l->a, r->a);
		b = max(l->b, r->b);
		c = max(l->c, r->c);
		ab = max(l->ab, r->ab);
		bc = max(l->bc, r->bc);
		ac = max(l->ac, r->ac);
		abc= max(l->abc, r->abc);
	}
	int bsa(int x) { // find last element a > x
		prop();
		if(s == e) return s;
		else if(r->a > x) return r->bsa(x);
		else return l->bsa(x);
	}
	int bsb(int x) {
		prop();
		if(s == e) return s;
		else if(r->b > x) return r->bsb(x);
		else return l->bsb(x);
	}
} *root;
		

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, ans = 0;
	cin >> n;
	int a[n], b[n];
	for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
	root = new node(0, n-1);
	for(int i = n-1; i >= 0; i--) {
		root->raddc(i, n-1, 1);
		root->rseta(i, max(i, root->bsa(a[i])), a[i]);
		root->rsetb(i, max(i, root->bsb(b[i])), b[i]);
		ans = max(ans, root->abc);
	}
	cout << ans << '\n';
}

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