oj.uz

Submission #321770

# Submission time Handle Problem Language Result Execution time Memory
321770 2020-11-13T10:34:36 Z alextodoran 3D Histogram (COCI20_histogram) C++17
20 / 110
 2500 ms 5952 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200002;
const int L_MAX = 1000002;

int n;

int a[N_MAX], b[N_MAX];

vector <pair <int, int> > vp;

vector <int> st;

int L[N_MAX], R[N_MAX];

int a1[N_MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    for(int i = 1; i <= n; i++)
        vp.push_back(make_pair(b[i], i));
    sort(vp.begin(), vp.end());
    reverse(vp.begin(), vp.end());
    a1[0] = a1[n + 1] = -1;
    ll ans = 0;
    for(pair <int, int> p : vp)
    {
        int x = p.second;
        a1[x] = a[x];
        st.push_back(0);
        for(int i = 1; i <= n; i++)
        {
            while(a1[st.back()] >= a1[i])
                st.pop_back();
            L[i] = i - st.back() - 1;
            st.push_back(i);
        }
        st.clear();
        st.push_back(n + 1);
        for(int i = n; i >= 1; i--)
        {
            while(a1[st.back()] >= a1[i])
                st.pop_back();
            R[i] = st.back() - i - 1;
            st.push_back(i);
        }
        st.clear();
        for(int i = 1; i <= n; i++)
            ans = max(ans, 1LL * b[x] * a1[i] * (L[i] + R[i] + 1));
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 332 KB Output is correct
2 Correct 46 ms 332 KB Output is correct
3 Correct 34 ms 332 KB Output is correct
4 Correct 34 ms 332 KB Output is correct
5 Correct 31 ms 332 KB Output is correct
6 Correct 45 ms 332 KB Output is correct
7 Correct 31 ms 332 KB Output is correct
8 Correct 33 ms 392 KB Output is correct
9 Correct 40 ms 332 KB Output is correct
10 Correct 37 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 47 ms 360 KB Output is correct

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 332 KB Output is correct
2 Correct 46 ms 332 KB Output is correct
3 Correct 34 ms 332 KB Output is correct
4 Correct 34 ms 332 KB Output is correct
5 Correct 31 ms 332 KB Output is correct
6 Correct 45 ms 332 KB Output is correct
7 Correct 31 ms 332 KB Output is correct
8 Correct 33 ms 392 KB Output is correct
9 Correct 40 ms 332 KB Output is correct
10 Correct 37 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 47 ms 360 KB Output is correct
13 Execution timed out 2576 ms 5952 KB Time limit exceeded
14 Halted 0 ms 0 KB -