oj.uz

Submission #479417

# Submission time Handle Problem Language Result Execution time Memory
479417 2021-10-11T16:59:05 Z ocarima 3D Histogram (COCI20_histogram) C++14
0 / 110
 1 ms 332 KB 
#include<bits/stdc++.h>

using namespace std;

// Problema E, div2 747

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define lli long long int
#define vi vector<int>
#define vlli vector<long long int>
#define pii pair<int, int>
#define plli pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define repv(x, v) for(auto x : v)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(x) cout << #x << " = " << x << ", "
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b) cout << x[i] << ", "; cout << "]\n"
#define pb push_back
#define nl "\n"

#define MAXN 200003

lli n, a[MAXN], b[MAXN], ab[MAXN], res;

lli divide_y_venceras(lli l, lli r){
    if (l < r) return 0;
    if (l == r) return a[l] * b[l];

    lli ans = 0;
    lli mitad = (l + r) / 2;

    // OBTEN LO MEJOR DE AMBAS MITADES
    ans = max(divide_y_venceras(l, mitad - 1), divide_y_venceras(mitad + 1, r));

    // OBTEN LO MEJOR QUE PASE POR EL CENTRO

    // CONSTRUYE LA GRAFICA DE (a * b) HACIA AMBOS LADOS
    lli mina, minb;
    mina = a[mitad];
    minb = b[mitad];
    ab[mitad] = mina * minb;
    repa(i, mitad - 1, l){
        mina = min(mina, a[i]);
        minb = min(minb, b[i]);
        ab[i] = mina * minb;
    }
    mina = a[mitad];
    minb = b[mitad];
    rep(i, mitad + 1, r){
        mina = min(mina, a[i]);
        minb = min(minb, b[i]);
        ab[i] = mina * minb;
    }

    // AUMENTA LA VENTANA HACIA AMBOS LADOS
    lli itl, itr, val;
    val = ab[mitad];
    itl = itr = mitad;
    while(l <= itl && itr <= r){
        while (l <= itl && ab[itl] == val) --itl;
        while (itr <= r && ab[itr] == val) ++itr;
        ans = max(ans, val * (itr - itl - 1));
        val = min(ab[itl], ab[itr]);
    }
}

int main()
{
    fastio;
    cin >> n;
    rep(i, 1, n) cin >> a[i] >> b[i];
    res = divide_y_venceras(1, n);
    cout << res;
}

Compilation message

histogram.cpp: In function 'long long int divide_y_venceras(long long int, long long int)':
histogram.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -