Submission #441862

#	Time	Username	Problem	Language	Result	Execution time	Memory
441862		leaked	Bomb (IZhO17_bomb)	C++14	58 / 100	1095 ms	87288 KiB

bomb

#include <bits/stdc++.h>

#define vec vector
#define sz(x) (short int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long long ll;
typedef pair<ll,short int> pli;
typedef pair<short int,ll> pil;
typedef pair<short int,short int> pii;
auto rng=bind(uniform_int_distribution<short int>(1,32000),mt19937(time(0)));
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const short int N=2503;
void mg(vec<pii> &a,vec<pii> &b,vec<array<short int,3>> &arr){
    int n=sz(a),m=sz(b);
    int i=0,j=0;
    short int mn=32000,mx=-32000,h=32000;
    arr.clear();
//    debug()<<imie(a)imie(b);
    for(short int k=0;k<n+m;k++){
        if((j==m) || (i!=n && a[i].f>b[j].f)) h=a[i].f,umin(mn,a[i++].s);
        else h=b[j].f,umax(mx,b[j++].s);
//        debug()<<imie(mn)imie(mx);
        if(mn!=32000 && mx!=-32000)arr.pb({mn,mx,h});
    }
//    debug()
    a.clear();b.clear();
}
short int up[N][N],dn[N][N],n,m;
short int lft1[N][N],rgt1[N][N],lft2[N][N],rgt2[N][N],a[N][N];
bool cmp(const array<short int,3> &f,const array<short int,3> &s){
    if(f[0]==s[0]){
        return f[1]>s[1];
    }
    return f[0]<s[0];
}
int tt;
int lst[N],mxm[N];
short int fck[N];
void do_this(vec<array<short int,3>> &x1,vec<array<short int,3>> &x2){
    tt++;
    reverse(all(x1));
    reverse(all(x2));
    /// now let us go by left
    short int r=32000,h1=-1;
    short int l=-32000,h2=-1;
    short int x=sz(x1),y=sz(x2);
    int blya=x+y;
    int _i=0,_j=0;
    vec<short int>lng;
    while(blya--){
        if(_i!=x && (_j==y || cmp(x1[_i],x2[_j]))){
            umax(l,x1[_i][0]);
            umin(r,x1[_i][1]);
            umax(h1,x1[_i][2]);
            _i++;
        }
        else{
            umax(l,x2[_j][0]);
            umin(r,x2[_j][1]);
            umax(h2,x2[_j][2]);
            _j++;
        }
        short int dl=r-l+1;
        if(!_i || !_j) continue;
        short int _h=h1+h2-1;
        if(lst[dl]!=tt){
            lst[dl]=tt;fck[dl]=-1;lng.pb(dl);
        }
        umax(fck[dl],_h);
    }
    reverse(all(lng));
    short int g=0;
    for(auto &z : lng){
        umin(mxm[g+1],(int)fck[z]);
        g=z;
    }
    return;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    cin>>n>>m;
    for(short int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(short int j=0;j<m;j++){
            a[i][j+1]=s[j]-'0';
        }
    }
    for(int i=1;i<=m;i++){
        mxm[i]=1e9;
    }
    for(short int i=n;i>=1;i--){
        for(short int j=m;j>=1;j--){
            if(a[i][j]) dn[i][j]=dn[i+1][j]+1;
        }
    }
    for(short int i=1;i<=n;i++){
        for(short int j=m;j>=1;j--){
            if(a[i][j]) up[i][j]=up[i-1][j]+1;
        }
    }
    vec<pii>vc;
    for(short int i=1;i<=n;i++){
        vc.pb({-1,0});
        for(short int j=1;j<=m;j++){
            while(sz(vc) && vc.back().f>=up[i][j]) vc.pop_back();
            lft1[i][j]=vc.back().s;
            vc.pb({up[i][j],j});
        }
        vc.clear();
        vc.pb({-1,m+1});
        for(short int j=m;j>=1;j--){
            while(sz(vc) && vc.back().f>=up[i][j]) vc.pop_back();
            rgt1[i][j]=vc.back().s;
            vc.pb({up[i][j],j});
        }
    }
    for(short int i=1;i<=n;i++){
        vc.clear();
        vc.pb({-1,0});
        for(short int j=1;j<=m;j++){
            while(sz(vc) && vc.back().f>=dn[i][j]) vc.pop_back();
            lft2[i][j]=vc.back().s;
            vc.pb({dn[i][j],j});
        }
        vc.clear();
        vc.pb({-1,m+1});
        for(short int j=m;j>=1;j--){
            while(sz(vc) && vc.back().f>=dn[i][j]) vc.pop_back();
            rgt2[i][j]=vc.back().s;
            vc.pb({dn[i][j],j});
        }
    }
    vec<array<short int,3>>x1,x2;
    vec<pii>vc1,vc2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!a[i][j])continue;
//            debug()<<imie(i)imie(j);
            {
            short int u=j;
            while(u!=0){
                vc1.pb({up[i][u],lft1[i][u]+1});
                u=lft1[i][u];
            }
            u=j;
            while(u!=m+1){
                vc2.pb({up[i][u],rgt1[i][u]-1});
                u=rgt1[i][u];
            }
//            debug()<<imie(vc1)imie(vc2);
            mg(vc1,vc2,x1);
//            debug()<<imie(x1);
            u=j;
            while(u!=0){
                vc1.pb({dn[i][u],lft2[i][u]+1});
                u=lft2[i][u];
            }
            u=j;
            while(u!=m+1){
                vc2.pb({dn[i][u],rgt2[i][u]-1});
                u=rgt2[i][u];
            }
            mg(vc1,vc2,x2);
            }
            do_this(x1,x2);
//            debug()<<imie(x1)imie(x2);
        }
    }
    for(short int i=2;i<=m;i++) umin(mxm[i],mxm[i-1]);
    int ans=0;
    for(short int i=1;i<=m;i++){
        umax(ans,i*mxm[i]);
    }
    cout<<ans;
    return 0;
}

/*
10
2 1 2 2 1 1 3 2 5 5
*/

• Subtask 1: 58 / 100