Submission #1107191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107191		lmToT27	3D Histogram (COCI20_histogram)	C++17	110 / 110	470 ms	40216 KiB

histogram

#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()

typedef long long ll;

using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}

const int MAX = 2e5 + 3;
const ll MOD[] = {1000000007, 998244353};

int n;
ll a[MAX], b[MAX];
ll A[MAX], B[MAX];

struct eq_t {
        ll a, b;

        eq_t(ll a = 0, ll b = 0) : a(a), b(b) {}

        bool operator < (const eq_t &other) const {
                return a < other.a;
        }

        ll operator () (ll x) {
                return a * x + b;
        }
};

bool bad(eq_t A, eq_t B, eq_t C) {
        return (A.a - C.a) * (A.b - B.b) <= (A.a - B.a) * (A.b - C.b);
}

vector <eq_t> st[MAX << 2];

void modify(vector <eq_t> &f) {
        sort(all(f));
        vector <eq_t> hull;
        for (auto &x : f) {
                while (hull.size() >= 2 && bad(hull[(int)hull.size() - 2], hull.back(), x)) hull.pop_back();
                hull.push_back(x);
        }
        f = hull;
}

void build(int i, int id, int l, int r) {
        st[id].clear();
        if (l == r) {
                st[id].push_back(eq_t(B[l], B[l] * abs(l - i)));
        } else {
                int mid = (l + r) / 2;
                build(i, id << 1, l, mid);
                build(i, id << 1 | 1, mid + 1, r);
                st[id] = st[id << 1];
                for (auto &x : st[id << 1 | 1]) st[id].push_back(x);
                modify(st[id]);
        }
}

ll getMax(ll x, int u, int v, int id, int l, int r) {
        if (u > v || v < l || r < u) return 0;
        if (u <= l && r <= v) {
                if (st[id].empty()) return 0;
                ll res = st[id][0](x), optL, optR;
                int L = 0, R = (int)st[id].size() - 2, mid;
                // for (auto &f : st[id]) res = max(res, f(x));
                while (L < R) {
                        mid = (L + R) / 2;
                        optL = st[id][mid](x);
                        optR = st[id][mid + 1](x);
                        res = max({res, optL, optR});
                        if (optL < optR) L = mid + 1;
                        else R = mid;
                }
                return res;
        }
        int mid = (l + r) / 2;
        return max(getMax(x, u, v, id << 1, l, mid), getMax(x, u, v, id << 1 | 1, mid + 1, r));
}

ll dnc(int L, int R) {
        if (L == R) return a[L] * b[L];
        int mid = (L + R) / 2;
        ll res = max(dnc(L, mid), dnc(mid + 1, R));
        
        A[mid] = a[mid];
        B[mid] = b[mid];
        A[mid + 1] = a[mid + 1];
        B[mid + 1] = b[mid + 1];

        for (int i = mid - 1; i >= L; i--) {
                A[i] = min(A[i + 1], a[i]);
                B[i] = min(B[i + 1], b[i]);
        }

        for (int i = mid + 2; i <= R; i++) {
                A[i] = min(A[i - 1], a[i]);
                B[i] = min(B[i - 1], b[i]);
        }

        if (1) {
                int l = mid, r = mid;
                build(mid, 1, mid + 1, R);
                for (int i = mid; i >= L; i--) {
                        while (r < R && A[r + 1] >= A[i]) r++;
                        while (l < r && B[l + 1] >= B[i]) l++;

                        res = max(res, A[i] * B[i] * (l - i + 1));
                        // for (int j = l + 1; j <= r; j++) {
                        //         cout << B[j] << ' ' << B[j] * (j - mid) << '\n';
                        //         res = max(res, A[i] * B[j] * (j - i + 1));
                        // }
                        res = max(res, A[i] * getMax(mid  - i + 1, l + 1, r, 1, mid + 1, R));             
                }
        }

        if (1) {
                int l = mid + 1, r = mid + 1;
                build(mid + 1, 1, L, mid);
                for (int i = mid + 1; i <= R; i++) {
                        while (l > L && A[l - 1] >= A[i]) l--;
                        while (r > l && B[r - 1] >= B[i]) r--;

                        res = max(res, A[i] * B[i] * (i - r + 1));
                        // for (int j = l; j < r; j++) res = max(res, A[i] * B[j] * (i - j + 1));
                        res = max(res, A[i] * getMax(i - mid, l, r - 1, 1, L, mid));
                }
        }

        return res;
}

ll bruteForce() {
        ll res = 0;
        for (int i = 1; i <= n; i++) {
                ll A = a[i], B = b[i];
                for (int j = i; j <= n; j++) {
                        A = min(A, a[j]);
                        B = min(B, b[j]);
                        res = max(res, A * B * (j - i + 1));
                }
        }
        return res;
}

void Solve() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
                cin >> a[i] >> b[i];
        }
        if (n <= 2000) return void(cout << bruteForce()); 
        cout << dnc(1, n);
}

int32_t main() {
        std::ios_base::sync_with_stdio(0);
        std::cin.tie(0); std::cout.tie(0);

        #define TASK ""
        if (fopen(TASK".INP", "r")) {
                freopen(TASK".INP", "r", stdin);
                freopen(TASK".OUT", "w", stdout);
        }
        
        if (fopen("TASK.INP", "r")) {
                freopen("TASK.INP", "r", stdin);
                freopen("TASK.OUT", "w", stdout);
        }
        
        /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

        cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
        return 0;
}

Compilation message (stderr)

histogram.cpp: In function 'int32_t main()':
histogram.cpp:174:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |                 freopen(TASK".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:175:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |                 freopen(TASK".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:179:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:180:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |                 freopen("TASK.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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