oj.uz

Submission #314863

# Submission time Handle Problem Language Result Execution time Memory
314863 2020-10-21T14:21:35 Z model_code 3D Histogram (COCI20_histogram) C++17
110 / 110
 849 ms 67736 KB 
#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]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49680 KB Output is correct
2 Correct 33 ms 49692 KB Output is correct
3 Correct 30 ms 49668 KB Output is correct
4 Correct 36 ms 49624 KB Output is correct
5 Correct 37 ms 49712 KB Output is correct
6 Correct 35 ms 49596 KB Output is correct
7 Correct 31 ms 49616 KB Output is correct
8 Correct 31 ms 49708 KB Output is correct
9 Correct 30 ms 49636 KB Output is correct
10 Correct 40 ms 49672 KB Output is correct
11 Correct 26 ms 49476 KB Output is correct
12 Correct 39 ms 49676 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49680 KB Output is correct
2 Correct 33 ms 49692 KB Output is correct
3 Correct 30 ms 49668 KB Output is correct
4 Correct 36 ms 49624 KB Output is correct
5 Correct 37 ms 49712 KB Output is correct
6 Correct 35 ms 49596 KB Output is correct
7 Correct 31 ms 49616 KB Output is correct
8 Correct 31 ms 49708 KB Output is correct
9 Correct 30 ms 49636 KB Output is correct
10 Correct 40 ms 49672 KB Output is correct
11 Correct 26 ms 49476 KB Output is correct
12 Correct 39 ms 49676 KB Output is correct
13 Correct 627 ms 65232 KB Output is correct
14 Correct 665 ms 65924 KB Output is correct
15 Correct 712 ms 66012 KB Output is correct
16 Correct 700 ms 65900 KB Output is correct
17 Correct 767 ms 67600 KB Output is correct
18 Correct 649 ms 67676 KB Output is correct
19 Correct 666 ms 67212 KB Output is correct
20 Correct 692 ms 67648 KB Output is correct
21 Correct 626 ms 65944 KB Output is correct
22 Correct 622 ms 67736 KB Output is correct
23 Correct 69 ms 51104 KB Output is correct
24 Correct 849 ms 65044 KB Output is correct