oj.uz

답안 #366799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366799 2021-02-15T09:58:41 Z VEGAnn 3D Histogram (COCI20_histogram) C++14
110 / 110
 854 ms 67252 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

# 결과 실행 시간 메모리 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

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 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