#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
#define ls (x<<1)
#define rs (x<<1|1)
int gi() {
int x=0,o=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') o=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*o;
}
int n,m,q;
bool **a;
struct arr {
short *f;
void resize(int n) {
f=new short[n+11];
for(int i=0;i<=n;i++) f[i]=0;
}
short operator[](int x) const {
return f[x];
}
short& operator[](int x) {
return f[x];
}
};
struct dat {
arr f,up,bot;int len;
void resize(int n) {
f.resize(n);up.resize(n);bot.resize(n);
}
} tr[16000010];
struct mono_queue {
pii q[2010];int h=1,t=0;
void push(pii x) {
while(h<=t&&q[t].fi>=x.fi) --t;
q[++t]=x;
}
int query(int t) {
while(q[h].se<t) ++h;
return q[h].fi;
}
void clear() {
h=1;t=0;
}
} Q1,Q2;
int cnt=0;
dat operator+(dat a,dat b) {
dat ret;ret.resize(m);ret.len=a.len+b.len;
Q1.clear();Q2.clear();
for(int i=1,j=1;i<=m;i++) {
Q1.push(mp(a.bot[i],i));
Q2.push(mp(b.up[i],i));
while(j<=i&&Q1.query(j)+Q2.query(j)<i-j+1) ++j;
ret.f[i]=max(a.f[i],max(b.f[i],short(i-j+1)));
ret.up[i]=a.up[i]+(a.up[i]==a.len?b.up[i]:0);
ret.bot[i]=b.bot[i]+(b.bot[i]==b.len?a.bot[i]:0);
}
return ret;
}
dat getrow(int x) {
dat ret;ret.resize(m);ret.len=1;
for(int i=1;i<=m;i++) ret.f[i]=ret.up[i]=ret.bot[i]=a[x][i];
return ret;
}
void build(int x=1,int l=1,int r=n) {
++cnt;
if(l==r) { tr[x]=getrow(l);return; }
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
tr[x]=tr[ls]+tr[rs];
}
void modify(int p,int x=1,int l=1,int r=n) {
if(l==r) { tr[x]=getrow(l);return; }
int mid=(l+r)>>1;
p<=mid?modify(p,ls,l,mid):modify(p,rs,mid+1,r);
tr[x]=tr[ls]+tr[rs];
}
dat query(int L,int R,int x=1,int l=1,int r=n) {
if(L<=l&&r<=R) return tr[x];
int mid=(l+r)>>1;
if(R<=mid) return query(L,R,ls,l,mid);
if(L>mid) return query(L,R,rs,mid+1,r);
return query(L,R,ls,l,mid)+query(L,R,rs,mid+1,r);
}
int main() {
cin>>n>>m>>q;n=1e6;
a=new bool*[n+1];
for(int i=1;i<=n;i++) a[i]=new bool[m+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) a[i][j]=gi();
build();exit(0);//while(1);
/*while(q--) {
int op=gi();
if(!op) {
int x=gi(),y=gi();
a[x][y]^=1;modify(x);
}
else {
int l=gi(),s=gi(),r=gi(),t=gi();
short ans=0;
dat tmp=query(l,r);
for(int i=s;i<=t;i++) ans=max(ans,min(tmp.f[i],short(i-s+1)));
cout<<ans<<'\n';
}
}*/
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 26.878 ms | 103 MB + 728 KB | Runtime Error | Score: 0 | 显示更多 |