#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 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |