oj.uz

답안 #321780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321780 2020-11-13T11:03:57 Z alextodoran 3D Histogram (COCI20_histogram) C++17
0 / 110
 185 ms 269724 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;

bool active[N_MAX];

int root[N_MAX];

deque <int> stL[N_MAX], stR[N_MAX];

int lSide[N_MAX], rSide[N_MAX];

int L[N_MAX], R[N_MAX];

int findRoot (int u)
{
    if(root[u] == u)
        return u;
    return root[u] = findRoot(root[u]);
}

vector <int> recalc;

ll maxArea;

ll area (int i)
{
    return 1LL * (L[i] + R[i] + 1) * a[i];
}

void simL (int ls, deque <int> dq1, deque <int> &dq2)
{
    reverse(dq2.begin(), dq2.end());
    for(int i : dq2)
    {
        while(dq1.empty() == false && a[dq1.back()] >= a[i])
            dq1.pop_back();
        if(dq1.empty() == true)
            L[i] = i - ls;
        else
            L[i] = i - dq1.back() - 1;
        dq1.push_back(i);
        recalc.push_back(i);
    }
    reverse(dq2.begin(), dq2.end());
}
void simR (int rs, deque <int> dq1, deque <int> &dq2)
{
    reverse(dq2.begin(), dq2.end());
    for(int i : dq2)
    {
        while(dq1.empty() == false && a[dq1.back()] >= a[i])
            dq1.pop_back();
        if(dq1.empty() == true)
            R[i] = rs - i;
        else
            R[i] = dq1.back() - i - 1;
        dq1.push_back(i);
        recalc.push_back(i);
    }
    reverse(dq2.begin(), dq2.end());
}

void join (int u, int v)
{
    u = findRoot(u);
    v = findRoot(v);
    simL(lSide[u], stL[u], stR[v]);
    simR(rSide[v], stR[v], stL[u]);
    while(stL[u].empty() == false && a[stL[u].back()] >= a[stL[v].front()])
        stL[u].pop_back();
    while(stR[v].empty() == false && a[stR[v].back()] >= a[stR[u].front()])
        stR[v].pop_back();
    if((int)stL[u].size() < (int)stL[v].size())
    {
        while(stL[u].empty() == false)
        {
            stL[v].push_front(stL[u].back());
            stL[u].pop_back();
        }
    }
    else
    {
        while(stL[v].empty() == false)
        {
            stL[u].push_back(stL[v].front());
            stL[v].pop_front();
        }
        swap(stL[u], stL[v]);
    }
    if((int)stR[u].size() < (int)stR[v].size())
    {
        while(stR[u].empty() == false)
        {
            stR[v].push_back(stR[u].front());
            stR[u].pop_front();
        }
    }
    else
    {
        while(stR[v].empty() == false)
        {
            stR[u].push_front(stR[v].back());
            stR[v].pop_back();
        }
        swap(stR[u], stR[v]);
    }
    root[u] = v;
    lSide[v] = lSide[u];
}

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());
    for(int i = 1; i <= n; i++)
    {
        root[i] = i;
        active[i] = false;
        stL[i].push_back(i);
        stR[i].push_back(i);
        L[i] = R[i] = 0;
        lSide[i] = rSide[i] = i;
    }
    ll ans = 0;
    for(pair <int, int> p : vp)
    {
        int i = p.second;
        active[i] = true;
        if(i > 1 && active[i - 1] == true)
            join(i - 1, i);
        if(i < n && active[i + 1] == true)
            join(i, i + 1);
        recalc.push_back(i);
        for(int r : recalc)
            maxArea = max(maxArea, area(r));
        recalc.clear();
        ans = max(ans, maxArea * b[i]);
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 269724 KB Output is correct
2 Correct 160 ms 269688 KB Output is correct
3 Correct 160 ms 269636 KB Output is correct
4 Incorrect 185 ms 269708 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 269724 KB Output is correct
2 Correct 160 ms 269688 KB Output is correct
3 Correct 160 ms 269636 KB Output is correct
4 Incorrect 185 ms 269708 KB Output isn't correct
5 Halted 0 ms 0 KB -