Submission #331910

#	Time	Username	Problem	Language	Result	Execution time	Memory
331910		doowey	3D Histogram (COCI20_histogram)	C++14	110 / 110	905 ms	66364 KiB

histogram

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int>pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 100;
const ld inf = (2e18);

struct Line{
    ld A;
    ld B;
    ld lim;
};

ld cross(Line aa, Line bb){
    return (aa.B-bb.B)/(bb.A-aa.A);
}

struct Hull{
    vector<Line> pq;
    void append(Line cur){
        if(!pq.empty()){
            if(pq.back().A == cur.A){
                if(pq.back().B >= cur.B) return;
                pq.pop_back();
            }
            // no two paralel lines
            while(pq.size() >= 2 && cross(pq[pq.size() - 2], cur) <= cross(pq[pq.size() - 2], pq[pq.size() - 1])){
                pq.pop_back();
            }
        }
        if(!pq.empty()){
            pq.back().lim = cross(pq.back(), cur);
        }
        pq.push_back(cur);
    }
    int it = 0;
    ll get(ll val){
        while(pq[it].lim < val)
            it ++ ;
        return pq[it].A*1ll*val+pq[it].B;
    }
};

ll x[N];
ll y[N];

ll sol = 0;

struct ele{
    ll ff;
    ll gg;
    ll cnt;
};

Hull segt[N * 4 + 512];
Line faf[N];

void build(int node, int cl, int cr){
    segt[node].pq.clear();
    segt[node].it=0;
    for(int i = cr; i >= cl; i -- ){
        segt[node].append(faf[i]);
    }
    if(cl==cr)return;
    int mid = (cl+cr)/2;
    build(node*2,cl,mid);
    build(node*2+1,mid+1,cr);
}

ll qry(int node, int cl, int cr, int tl, int tr, ll qa){
    if(cr < tl || cl > tr) return 0;
    if(cl >= tl && cr <= tr){
        return segt[node].get(qa);
    }
    int mid = (cl+cr)/2;
    return max(qry(node*2,cl,mid,tl,tr,qa),qry(node*2+1,mid+1,cr,tl,tr,qa));
}

void upd(vector<ele> f1, vector<ele> f2){
    int ii = -1;
    for(int i = 0 ; i < f2.size(); i ++ ){
        while(ii + 1 < f1.size() && f1[ii+1].ff >= f2[i].ff && f1[ii+1].gg >= f2[i].gg){
            ii ++ ;
        }
        if(ii>=0)
            sol = max(sol,(f2[i].cnt+f1[ii].cnt)*1ll*f2[i].ff*1ll*f2[i].gg);
    }
    for(int i = 0 ; i < f2.size(); i ++ ){
        faf[i] = {f2[i].gg,f2[i].gg*1ll*f2[i].cnt,inf};
    }
    build(1, 0, f2.size() - 1);
    ii = -1;
    int jj = 0;
    for(int i = 0 ; i < f1.size(); i ++ ){
        while(ii + 1 < f2.size() && f2[ii + 1].ff >= f1[i].ff)
            ii ++ ;
        while(jj < f2.size() && f2[jj].gg > f1[i].gg){
            jj ++ ;
        }
        if(jj <= ii){
            sol = max(sol, qry(1, 0, f2.size() - 1, jj,ii,f1[i].cnt) * 1ll * f1[i].ff);
        }
    }
}

void solve(int lf, int rf){
    if(lf >= rf) return;
    int mid = (lf + rf) / 2;
    ele cur = {(ll)1e9, (ll)1e9, 0};
    vector<ele> pp, qq;
    for(int i = mid; i >= lf ; i -- ){
        cur.ff=min(cur.ff,x[i]);
        cur.gg=min(cur.gg,y[i]);
        cur.cnt++;
        pp.push_back(cur);
    }
    cur = {(ll)1e9, (ll)1e9, 0};
    for(int i = mid + 1; i <= rf; i ++ ){
        cur.ff=min(cur.ff,x[i]);
        cur.gg=min(cur.gg,y[i]);
        cur.cnt++;
        qq.push_back(cur);
    }
    upd(pp,qq);
    upd(qq,pp);
    solve(lf, mid);
    solve(mid+1, rf);

}

int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> x[i] >> y[i];
        sol = max(sol, x[i] * 1ll * y[i]);
    }
    solve(1, n);
    cout << sol << "\n";
    return 0;
}

Compilation message (stderr)

histogram.cpp: In function 'void upd(std::vector<ele>, std::vector<ele>)':
histogram.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i = 0 ; i < f2.size(); i ++ ){
      |                     ~~^~~~~~~~~~~
histogram.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         while(ii + 1 < f1.size() && f1[ii+1].ff >= f2[i].ff && f1[ii+1].gg >= f2[i].gg){
      |               ~~~~~~~^~~~~~~~~~~
histogram.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i = 0 ; i < f2.size(); i ++ ){
      |                     ~~^~~~~~~~~~~
histogram.cpp:98:25: warning: narrowing conversion of 'f2.std::vector<ele>::operator[](((std::vector<ele>::size_type)i)).ele::gg' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   98 |         faf[i] = {f2[i].gg,f2[i].gg*1ll*f2[i].cnt,inf};
histogram.cpp:98:40: warning: narrowing conversion of '((f2.std::vector<ele>::operator[](((std::vector<ele>::size_type)i)).ele::gg * 1) * f2.std::vector<ele>::operator[](((std::vector<ele>::size_type)i)).ele::cnt)' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   98 |         faf[i] = {f2[i].gg,f2[i].gg*1ll*f2[i].cnt,inf};
histogram.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0 ; i < f1.size(); i ++ ){
      |                     ~~^~~~~~~~~~~
histogram.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         while(ii + 1 < f2.size() && f2[ii + 1].ff >= f1[i].ff)
      |               ~~~~~~~^~~~~~~~~~~
histogram.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while(jj < f2.size() && f2[jj].gg > f1[i].gg){
      |               ~~~^~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 90 / 90