oj.uz

Submission #316166

# Submission time Handle Problem Language Result Execution time Memory
316166 2020-10-25T16:12:57 Z georgerapeanu 3D Histogram (COCI20_histogram) C++11
0 / 110
 35 ms 2204 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5;

long long det(pair<int,int> a,pair<int,int> b,pair<int,int> c){
    return 1LL * a.first * (b.second - c.second) + 1LL * b.first * (c.second - a.second) + 1LL * c.first * (a.second - b.second);
}

bool cmp(pair<int,int> a,pair<int,int> b){
    return det(make_pair(0,0),a,b) > 0;
}

struct node_t{

    int lst_ind;
    vector<pair<long long,long long> > points;

    node_t operator + (const node_t &other)const{
        node_t ans;
        ans.lst_ind = 0;
        for(auto it:points){
            ans.points.push_back(it);
        }
        for(auto it:other.points){
            ans.points.push_back(it);
        }
        sort(ans.points.begin(),ans.points.end(),cmp);

        vector<pair<long long,long long> > tmp;
        tmp.push_back({0,0});

        for(auto it:ans.points){
            while((int)tmp.size() > 2 && det(tmp[(int)tmp.size() - 2],tmp[(int)tmp.size() - 1],it) < 0){
                tmp.pop_back();
            }
            tmp.push_back(it);
        }
        reverse(tmp.begin(),tmp.end());
        tmp.pop_back();
        reverse(tmp.begin(),tmp.end());
        ans.points.swap(tmp);
        return ans;
    }

    long long query(pair<long long,long long> v){
        while(lst_ind + 1 < (int)points.size() && points[lst_ind].first * v.first + points[lst_ind].first * v.second <= points[lst_ind + 1].first * v.first + points[lst_ind + 1].second * v.second){
            lst_ind++;
        }
        return points[lst_ind].first * v.first + points[lst_ind].second * v.second;
    }

    node_t(){
        lst_ind = 0;
        points = vector<pair<long long,long long> >();
    }

};

class SegmentTree{
    int n;
    vector<node_t> aint;

    void build(int nod,int st,int dr,vector<pair<long long,long long> > &v){
        if(st == dr){
            aint[nod].points = {v[st]};
            return ;
        }
        
        int mid = (st + dr) / 2;
        
        build(nod * 2,st,mid,v);
        build(nod * 2 + 1,mid + 1,dr,v);

        aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
    }

    long long query(int nod,int st,int dr,int l,int r,pair<long long,long long> v){
        if(dr < l || st > r){
            return 0;
        }

        if(l <= st && dr <= r){
            return aint[nod].query(v);
        }

        int mid = (st + dr) / 2;
        return max(query(nod * 2,st,mid,l,r,v),query(nod * 2 + 1,mid + 1,dr,l,r,v));
    }

    public:

    SegmentTree(int n,vector<pair<long long,long long> > v){
        this->n = n;
        this->aint = vector<node_t>(4 * n + 5,node_t());
        build(1,1,n,v);
    }
    
    long long query(int l,int r,pair<long long,long long> v){
        return query(1,1,n,l,r,v);
    }

};

int n;
int a[NMAX + 5];
int b[NMAX + 5];

long long solve(int st,int dr){
    if(st == dr){
        return 1LL * a[st] * b[st];
    }

    int mid = (st + dr) / 2;

    long long ans = max(solve(st,mid),solve(mid + 1,dr));

    int mi_a = 1e9;
    int mi_b = 1e9;

    int i_a = mid;
    int i_b = mid;
    int i2_b = mid;

    vector<pair<long long,long long> > points = {};

    int mip_b = 1e9;

    for(int i = mid;i >= st;i--){
        mip_b = min(mip_b,b[i]);
        points.push_back({1LL * mip_b,1LL * mip_b * (1 - i)});
    }
    points.push_back({0LL,0LL});
    reverse(points.begin(),points.end());

    SegmentTree aint(mid - st + 1,points);

    for(int i = mid + 1;i <= dr;i++){
        mi_a = min(mi_a,a[i]);
        mi_b = min(mi_b,b[i]);
        while(i_a >= st && a[i_a] >= mi_a){
            i_a--;
        }
        while(i_b >= st && b[i_b] > mi_b){
            i_b--;
        }
        while(i2_b >= st && b[i2_b] >= mi_b){
            i2_b--;
        }
        if(i_a <= i2_b){
            ans = max(ans,1LL * mi_a * mi_b * (i - i2_b));
        }
        if(i_a + 1 <= i_b){
            ans = max(ans,aint.query(i_a + 1 - (st - 1),i_b - (st - 1),make_pair(1LL * mi_a * i,1LL * mi_a)));
        }
        ///[i_a + 1,i_b]
    }
    return ans;
}

int main(){

    scanf("%d",&n);

    for(int i = 1;i <= n;i++){
        scanf("%d %d",&a[i],&b[i]);
    }

    long long ans = 0;

    ans = max(ans,solve(1,n));
    ans = max(ans,solve(1,n));swap(a,b);
    ans = max(ans,solve(1,n));reverse(a + 1,a + 1 + n);reverse(b + 1,b + 1 + n);
    ans = max(ans,solve(1,n));swap(a,b);

    printf("%lld\n",ans);

    return 0;
}

Compilation message

histogram.cpp: In function 'int main()':
histogram.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
histogram.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         scanf("%d %d",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2156 KB Output is correct
2 Correct 27 ms 2180 KB Output is correct
3 Correct 20 ms 2204 KB Output is correct
4 Incorrect 35 ms 2160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2156 KB Output is correct
2 Correct 27 ms 2180 KB Output is correct
3 Correct 20 ms 2204 KB Output is correct
4 Incorrect 35 ms 2160 KB Output isn't correct
5 Halted 0 ms 0 KB -