提交记录 12385


用户 题目 状态 得分 用时 内存 语言 代码长度
newbie314159 test. 自定义测试 Runtime Error 0 26.878 ms 106200 KB C++ 2.55 KB
提交时间 评测时间
2020-04-03 21:11:07 2023-09-03 19:40:00
#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;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #126.878 ms103 MB + 728 KBRuntime ErrorScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 00:17:00 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用