#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " = " << x << endl
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
typedef long long int llint;
typedef pair<llint, llint> par;
#define X first
#define Y second
const int MAXN = 5e5 + 10;
const int OFF = 1 << 21;
llint ccw(par a, par b, par c) {
return a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y);
}
int n;
int A[MAXN], B[MAXN];
llint rj;
// to je onaj slucaj kad mi lijeva granica l intervla
// [l, r] odredjuje minimum na intervalu za oba niza A i B
// dakle, treba napraviti foru s 2 pointera
void prvi_slucaj(int lo, int mid, int hi) {
int r = mid;
int a_mini = A[mid], b_mini = B[mid];
for(int l = mid; l >= lo; l--) {
a_mini = min(a_mini, A[l]);
b_mini = min(b_mini, B[l]);
while(r < hi && A[r + 1] >= a_mini && B[r + 1] >= b_mini) r++;
rj = max(rj, (llint) a_mini * b_mini * (r - l + 1));
}
}
vector<par> tocke;
int off;
vector<par> hullovi[OFF];
int trenutni[OFF];
void obrisi_stari_tournament() {
REP(i, 2 * off)
hullovi[i].clear();
}
void rekurzivno_izradi_hullove(int cvor, int a, int b) {
if(a == b) {
if(a < (int) tocke.size())
hullovi[cvor].push_back(tocke[a]);
trenutni[cvor] = (int) hullovi[cvor].size() - 1;
return;
}
rekurzivno_izradi_hullove(2 * cvor, a, (a + b) / 2);
rekurzivno_izradi_hullove(2 * cvor + 1, (a + b) / 2 + 1, b);
hullovi[cvor] = hullovi[2 * cvor];
int poc = (a + b) / 2 + 1, kraj = min(b + 1, (int) tocke.size());
FOR(i, poc, kraj) {
int sz = (int) hullovi[cvor].size();
while(sz >= 2 && ccw(hullovi[cvor][sz - 2], hullovi[cvor][sz - 1], tocke[i]) <= 0) {
hullovi[cvor].pop_back();
sz--;
}
hullovi[cvor].push_back(tocke[i]);
}
trenutni[cvor] = (int) hullovi[cvor].size() - 1;
}
void izgradi_tournament_hullova() {
for(off = 1; off < (int) tocke.size(); off *= 2);
obrisi_stari_tournament();
rekurzivno_izradi_hullove(1, 0, off - 1);
}
//prilagodjeni dp, buduci da je query tocka uvijek oblika (t, 1)
llint dp(int t, par a) {
return t * a.X + a.Y;
}
llint ispitaj_hull(int cvor, int t) {
if(trenutni[cvor] == -1) return 0;
while(trenutni[cvor] > 0 && dp(t, hullovi[cvor][trenutni[cvor] - 1]) >= dp(t, hullovi[cvor][trenutni[cvor]]))
trenutni[cvor]--;
return dp(t, hullovi[cvor][trenutni[cvor]]);
}
llint query(int cvor, int a, int b, int lo, int hi, int t) {
if(a > hi || b < lo) return 0;
if(a >= lo && b <= hi) return ispitaj_hull(cvor, t);
llint lijevi = query(2 * cvor, a, (a + b) / 2, lo, hi, t);
llint desni = query(2 * cvor + 1, (a + b) / 2 + 1, b, lo, hi, t);
return max(lijevi, desni);
}
// to je kompliciraniji slucaj kad lijeva granica l
// intervala [l, r] odredjuje minimum za A,
// a densa r minimum za B
void treci_slucaj(int lo, int mid, int hi) {
//ovdje mislim na minimume na lijevoj strani
int a_mini = A[mid], b_mini = B[mid];
//pocetak i kraj intervala koji pridruzujemo trenutom l
//interval je oblika [poc, kraj]
int poc = mid, kraj = mid;
vector<par> intervali;
vector<int> faktori;
for(int l = mid; l >= lo; l--) {
a_mini = min(a_mini, A[l]);
b_mini = min(b_mini, B[l]);
while(kraj < hi && A[kraj + 1] >= a_mini) kraj++;
while(poc <= hi && B[poc] > b_mini) poc++;
intervali.push_back(par(poc - mid, kraj - mid));
faktori.push_back(a_mini);
}
//postavljam tocke nad kojima cu graditi hullove
tocke.clear();
int mini_desno = B[mid];
for(int r = mid; r <= hi; r++) {
mini_desno = min(mini_desno, B[r]);
tocke.push_back(par(mini_desno, (llint) mini_desno * (r + 1)));
}
izgradi_tournament_hullova();
//upiti:
for(int l = mid; l >= lo; l--) {
int i = mid - l;
rj = max(rj, (llint) faktori[i] * query(1, 0, off - 1, intervali[i].X, intervali[i].Y, -1 * l));
}
}
void divide_and_conquer(int lo, int hi, int lijevo) {
if(lo > hi) return;
if(lijevo) {
int mid = (lo + hi) / 2;
prvi_slucaj(lo, mid, hi);
treci_slucaj(lo, mid, hi);
if(lo == hi) return;
divide_and_conquer(lo, mid - 1, lijevo);
divide_and_conquer(mid + 1, hi, lijevo);
}
else { //desno
int mid = (lo + hi + 1) / 2;
prvi_slucaj(lo, mid, hi);
treci_slucaj(lo, mid, hi);
if(lo == hi) return;
divide_and_conquer(mid + 1, hi, lijevo);
divide_and_conquer(lo, mid - 1, lijevo);
}
}
void rijesi() {
divide_and_conquer(0, n - 1, 1);
reverse(A, A + n); reverse(B, B + n);
divide_and_conquer(0, n - 1, 0);
}
int main() {
scanf("%d", &n);
REP(i, n)
scanf("%d %d", &A[i], &B[i]);
rijesi();
printf("%lld\n", rj);
return 0;
}
Compilation message
histogram.cpp: In function 'int main()':
histogram.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
162 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
histogram.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | scanf("%d %d", &A[i], &B[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
49672 KB |
Output is correct |
| 2 |
Correct |
29 ms |
49648 KB |
Output is correct |
| 3 |
Correct |
29 ms |
49652 KB |
Output is correct |
| 4 |
Correct |
32 ms |
49732 KB |
Output is correct |
| 5 |
Correct |
28 ms |
49724 KB |
Output is correct |
| 6 |
Correct |
29 ms |
49716 KB |
Output is correct |
| 7 |
Correct |
28 ms |
49696 KB |
Output is correct |
| 8 |
Correct |
29 ms |
49612 KB |
Output is correct |
| 9 |
Correct |
28 ms |
49612 KB |
Output is correct |
| 10 |
Correct |
32 ms |
49696 KB |
Output is correct |
| 11 |
Correct |
34 ms |
49484 KB |
Output is correct |
| 12 |
Correct |
28 ms |
49612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
49672 KB |
Output is correct |
| 2 |
Correct |
29 ms |
49648 KB |
Output is correct |
| 3 |
Correct |
29 ms |
49652 KB |
Output is correct |
| 4 |
Correct |
32 ms |
49732 KB |
Output is correct |
| 5 |
Correct |
28 ms |
49724 KB |
Output is correct |
| 6 |
Correct |
29 ms |
49716 KB |
Output is correct |
| 7 |
Correct |
28 ms |
49696 KB |
Output is correct |
| 8 |
Correct |
29 ms |
49612 KB |
Output is correct |
| 9 |
Correct |
28 ms |
49612 KB |
Output is correct |
| 10 |
Correct |
32 ms |
49696 KB |
Output is correct |
| 11 |
Correct |
34 ms |
49484 KB |
Output is correct |
| 12 |
Correct |
28 ms |
49612 KB |
Output is correct |
| 13 |
Correct |
593 ms |
65228 KB |
Output is correct |
| 14 |
Correct |
587 ms |
65412 KB |
Output is correct |
| 15 |
Correct |
622 ms |
65468 KB |
Output is correct |
| 16 |
Correct |
629 ms |
65360 KB |
Output is correct |
| 17 |
Correct |
602 ms |
67120 KB |
Output is correct |
| 18 |
Correct |
581 ms |
67196 KB |
Output is correct |
| 19 |
Correct |
633 ms |
66744 KB |
Output is correct |
| 20 |
Correct |
571 ms |
67252 KB |
Output is correct |
| 21 |
Correct |
605 ms |
65440 KB |
Output is correct |
| 22 |
Correct |
647 ms |
67252 KB |
Output is correct |
| 23 |
Correct |
88 ms |
51128 KB |
Output is correct |
| 24 |
Correct |
854 ms |
65148 KB |
Output is correct |
