Submission #445466

#TimeUsernameProblemLanguageResultExecution timeMemory
445466grt3D Histogram (COCI20_histogram)C++17
110 / 110
158 ms15248 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...