洛谷 P3400 仓鼠窝
2024-09-05 18:18:41
卡常
#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int,int> pi;
int n,m,a[][];
int xx[][];
int t1[],lst[],r;
int ta,sz[];LL ans;
int f1[],dd[],nxt[],mem,sz1[];
inline void read(int &x)
{
x=; int f=; char ch=getchar();
while( (ch<'' || ch>'') && ch!='-') ch=getchar(); if(ch=='-') {f=-; ch=getchar();}
while(ch>='' && ch <='') x=x*+ch-'',ch=getchar();
x*=f;
}
int main()
{
int i,j,k,t,p;
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
read(a[i][j]);
a[i][j]^=;
if(a[i][j]==)
{
for(k=i;k>=;k--)
{
if(xx[k][j]) break;
xx[k][j]=i;
}
}
}
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
if(xx[i][j]==)
xx[i][j]=n+;
xx[i][j]-=i;
}
// for(i=1;i<=n;i++)
// {
// for(j=1;j<=m;j++)
// printf("%lld ",xx[i][j]);
// puts("");
// }
// return 0;
for(i=;i<=n;i++)
{
r=;
for(j=m;j>=;j--)
{
while(r&&xx[i][t1[r]]>xx[i][j]) lst[t1[r]]=j,r--;
t1[++r]=j;
}
while(r) lst[t1[r]]=,r--;
mem=;
for(j=;j<=m;j++) sz1[j]=,f1[j]=;
for(j=;j<=m;j++)
if(lst[j]!=)
dd[++mem]=j,nxt[mem]=f1[lst[j]],f1[lst[j]]=mem,sz1[lst[j]]++;
for(j=;j<=m;j++) sz[j]=;
for(j=m;j>=;j--) sz[j]+=sz1[j],sz[lst[j]]+=sz[j];
//for(j=1;j<=m;j++) printf("%lld ",lst[j]);
//puts("");
ta=;t=0x3f3f3f3f;
for(j=;j<=m;j++) t=min(t,xx[i][j]),ta+=t;
for(j=;j<=m;j++)
{
ans+=ta;
for(k=f1[j];k;k=nxt[k])
{
p=dd[k];
ta+=(sz[p]+)*(xx[i][p]-xx[i][lst[p]]);
}
ta-=xx[i][j];
}
}
printf("%lld",ans);
return ;
}
最新文章
- [No00006F]总结C#获取当前路径的各种方法
- AndroidManifest.xml详解(上)
- LightOJ 1234	Harmonic Number
- RTC实时时钟
- JavaScript重复元素处理
- Window 10通过网线和Wifi连接树莓派
- rac安装grid报INS-41112错误
- RabbitMq install on Centos6.3
- git分支--branch
- Stochastic Gradient Descent
- socket编程: TypeError: must be bytes or buffer, not str
- logstash安装及基础入门
- leetcode 131. Palindrome Partitioning 、132. Palindrome Partitioning II
- 535 5.7.8 Error: authentication failed: generic failure安装EMOS时SMTP测试报错
- 趣味工具figlet
- mysql 触发器(Trigger)简明总结和使用实例
- Python itertools.combinations 和 itertools.permutations 等价代码实现
- [HAOI2017模拟]囚人的旋律
- Linux 软件看门狗 watchdog 喂狗
- LINUX中的DNS服务---高速缓存DNS