Submission #370616

#TimeUsernameProblemLanguageResultExecution timeMemory
370616ne4eHbKa3D Histogram (COCI20_histogram)C++17
0 / 110
1 ms332 KiB
#include <bits/stdc++.h> using namespace std; #ifndef _LOCAL //#pragma GCC optimize("O3,Ofast") #else #pragma GCC optimize("O0") #endif template<typename t> inline void umin(t &a, const t b) {a = min(a, b);} template<typename t> inline void umax(t &a, const t b) {a = max(a, b);} typedef pair<int, int> pii; typedef long long ll; typedef long double ld; ll time() {return chrono::system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); #define ft first #define sd second #define len(f) int((f).size()) #define bnd(f) (f).begin(), (f).end() #define _ <<' '<< const int inf = 1e9 + 5; const ll inf64 = 4e18 + 5; const int md = 998244353; namespace MD { void add(int &a, const int b) {if((a += b) >= md) a -= md;} void sub(int &a, const int b) {if((a -= b) < 0) a += md;} int prod(const int a, const int b) {return ll(a) * b % md;} }; int n; const int N = 2e5 + 5; int a[N], b[N]; pii l[N], r[N]; ll ans; inline void upd(ll a, ll b, ll c) {umax(ans, a * b * c);} struct line { int a; ll b; int i, x; int X(const line &f) const { ll z = (f.b - b) / (a - f.a); return z > n ? n : z < 1 ? 1 : z; } }; deque<line> f; int opt; void add(pii &t, int i) { int a = t.sd; ll b = (ll)t.sd * (i + 1); line p{a, b, i, n}; for(;;) { if(f.empty()) { f.push_back(p); return; } line &li = f.back(); if(li.a == a) { li.i = i; return; } int x = li.X(p); if(x < li.x) { p.x = x; f.push_back(p); return; } f.pop_back(); } } void del(int i) { for(; !f.empty() && f.front().i <= i; f.pop_front()) if(opt) --opt; } void calc(pii *l, int n, pii *r, int m) { f.clear(); int fi{}, se{}; opt = 0; for(int i = 0; i < n; ++i) { while(fi < m && r[fi].ft >= l[i].ft) add(r[fi], fi++); while(se < fi && r[se].sd >= l[i].sd) del(se++); umin(opt, len(f) - 1); upd(l[i].ft, l[i].sd, se + i + 1); while(opt + 1 < len(f) && f[opt + 1].x >= i + 1) ++opt; if(~opt) umax(ans, l[i].ft * (f[opt].b + f[opt].a * ll(i + 1))); } } void calc(int L, int R) { int MD = L + R >> 1; if(L < MD) calc(L, MD); if(MD + 1 < R) calc(MD + 1, R); int A = +inf, B = +inf, n = 0, m = 0; for(int i = MD; i >= L; --i) { umin(A, a[i]); umin(B, b[i]); l[n++] = {A, B}; } A = +inf, B = +inf; for(int i = MD + 1; i <= R; ++i) { umin(A, a[i]); umin(B, b[i]); r[m++] = {A, B}; } calc(l, n, r, m); calc(r, m, l, n); } void solve() { cin >> n; ans = 0; for(int i = 0; i < n; ++i) cin >> a[i] >> b[i], upd(a[i], b[i], 1); calc(0, n - 1); cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef _LOCAL // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); #else system("color a"); freopen("in.txt", "r", stdin); int t; cin >> t; while(t--) #endif solve(); }

Compilation message (stderr)

histogram.cpp: In function 'void calc(pii*, int, pii*, int)':
histogram.cpp:84:59: warning: operation on 'fi' may be undefined [-Wsequence-point]
   84 |         while(fi < m && r[fi].ft >= l[i].ft) add(r[fi], fi++);
      |                                                         ~~^~
histogram.cpp:84:59: warning: operation on 'fi' may be undefined [-Wsequence-point]
histogram.cpp: In function 'void calc(int, int)':
histogram.cpp:94:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int MD = L + R >> 1;
      |              ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...