Submission #360192

#	Time	Username	Problem	Language	Result	Execution time	Memory
360192		MrRobot_28	3D Histogram (COCI20_histogram)	C++17	20 / 110	441 ms	36652 KiB

histogram

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans = 0;
const int N =2e5;
vector <pair <int, int> > tree[4 * N];
int a[N], b[N];
void calc1(int l, int m, int r)
{
    int it1 = m + 1;
    int mina = 1e9, minb = 1e9;
    for(int i = m; i >= l; i--)
    {
        mina = min(mina, a[i]);
        minb = min(minb, b[i]);
        while(it1 <= r && a[it1] >= mina && b[it1] >= minb)
        {
            it1++;
        }
        ans = max(ans, mina * (it1 - i) * minb);
    }
}
int uk[N * 4];
int preffix[N];
int preffix1[N];
double inter(pair <int, int> a, pair <int, int> b)
{
    return 1.0 * (b.second - a.second) / (a.first - b.first);
}
void add(int v, pair <int, int> x)
{
    while(tree[v].size() > 0 && tree[v].back().first == x.first)
    {
        tree[v].pop_back();
    }
    while(tree[v].size() > 1 && inter(tree[v].back(), tree[v][tree[v].size() - 2]) >= inter(tree[v][tree[v].size() - 2], x))
    {
        tree[v].pop_back();
    }
    tree[v].push_back(x);
}
void build1(int v, int l, int r)
{
    tree[v].clear();
    uk[v] = 0;
    if(l == r)
    {
        tree[v].push_back({preffix[l], preffix[l] * (l + 1)});
        return;
    }
    build1(v * 2, l, (r + l) / 2);
    build1(v * 2 + 1, (r + l) / 2 + 1, r);
    int j = 0;
    for(int i = 0; i < tree[v * 2].size(); i++)
    {
        while(j < tree[v * 2 + 1].size() && (tree[v * 2 + 1][j].first < tree[v * 2][i].first || tree[v * 2 + 1][j].first == tree[v * 2][i].first && tree[v * 2 +1][j].second < tree[v * 2][i].second))
        {
            add(v, tree[v * 2 + 1][j]);
            j++;
        }
        add(v, tree[v * 2][i]);
    }
    while(j < tree[v * 2 + 1].size())
    {
        add(v, tree[v * 2 + 1][j]);
        j++;
    }

}
int go_to1(int v, int l, int r, int al, int ar, int x)
{
    if(al > ar)
    {
        return 0;
    }
    if(l >= al && r <= ar)
    {
        while(uk[v] < tree[v].size() - 1 && inter(tree[v][uk[v]], tree[v][uk[v] + 1]) <= x)
        {
            uk[v]++;
        }
        pair <int, int> p = tree[v][uk[v]];
        return p.first * x + p.second;
    }
    else if(l <= ar && r >= al)
    {
        return max(go_to1(v * 2, l, (r + l) / 2, al, ar, x), go_to1(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, x));
    }
    return 0;
}
void calc2(int l, int m, int r)
{
    int minb = 1e9;
    int mina = 1e9;
    for(int i = m + 1; i <= r; i++)
    {
        minb = min(minb, b[i]);
        preffix[i - m - 1] = minb;
        mina = min(mina, a[i]);
        preffix1[i - m - 1] = mina;
    }
    build1(1, 0, r - m - 1);
    mina = minb = 1e9;
    int it1 = 0, it2 = 0;
    for(int i = m; i >= l; i--)
    {
        mina = min(mina, a[i]);
        minb = min(minb, b[i]);
        while(it1 < r - m && preffix1[it1] >= mina)
        {
            it1++;
        }
        while(it2 < r - m && preffix[it2] > minb)
        {
            it2++;
        }
        int t = go_to1(1, 0, r - m - 1, it2, it1 - 1, m - i  + 1);
        ans = max(ans, t * mina);
    }
}
void go_to(int v, int l, int r, bool fl)
{
    if(l > r)
    {
        return;
    }
    if(l == r)
    {
        ans = max(ans, a[l] * b[l]);
        return;
    }
        int m = (l + r)/ 2;
        calc1(l, m, r);
        calc2(l, m, r);
        if(l == r)
        {
            return;
        }
        go_to(v * 2,l, m - 1, fl);
        go_to(v * 2 + 1, m + 1, r, fl);
}
signed main()
{
 //   ios_base::sync_with_stdio(0);
   /// cin.tie(0);
   // cout.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
    }
    go_to(1, 0, n - 1, 1);
    reverse(a, a + n);
    reverse(b, b + n);
    go_to(1, 0, n - 1, 0);
    cout << ans;
    return 0;
}

Compilation message (stderr)

histogram.cpp: In function 'void build1(long long int, long long int, long long int)':
histogram.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0; i < tree[v * 2].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~
histogram.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while(j < tree[v * 2 + 1].size() && (tree[v * 2 + 1][j].first < tree[v * 2][i].first || tree[v * 2 + 1][j].first == tree[v * 2][i].first && tree[v * 2 +1][j].second < tree[v * 2][i].second))
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:56:146: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   56 |         while(j < tree[v * 2 + 1].size() && (tree[v * 2 + 1][j].first < tree[v * 2][i].first || tree[v * 2 + 1][j].first == tree[v * 2][i].first && tree[v * 2 +1][j].second < tree[v * 2][i].second))
histogram.cpp:63:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while(j < tree[v * 2 + 1].size())
      |           ~~^~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp: In function 'long long int go_to1(long long int, long long int, long long int, long long int, long long int, long long int)':
histogram.cpp:78:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         while(uk[v] < tree[v].size() - 1 && inter(tree[v][uk[v]], tree[v][uk[v] + 1]) <= x)
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~

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