提交上去显示第一个点第二个输出的数是1,但我把数据下载下来在本地测是对的。
代码:
#include<bits/stdc++.h>
#define ri register int
#define l first
#define r second
using namespace std;
inline void read(int &x)
{
x=0;char ch=getchar();
while('0'<=ch&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
}
int n,m,t,hh=1,tt;
int a[250001],q[500001];
pair<int,int> e[250001];
bool st[250001];
bool cmp(pair<int,int> a,pair<int,int> b)
{
if(a.l==b.l)return a.r>b.r;
return a.l<b.l;
}
int main()
{
// freopen("flow.in","r",stdin);
// freopen("flow.out","w",stdout);
read(n),read(m);
int c=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)read(a[++c]);
t^=c^=t^=c;
for(int i=1;i<=m;++i)q[++tt]=i;
while(hh<=tt){
int t=q[hh],x=(t-1)/m+1,y=(t-1)%m+1;
++hh;
if(y>1&&!st[t-1]&&a[t]>a[t-1])st[t-1]=1,q[++tt]=t-1;
if(y<m&&!st[t+1]&&a[t]>a[t+1])st[t+1]=1,q[++tt]=t+1;
if(x>1&&!st[t-m]&&a[t]>a[t-m])st[t-m]=1,q[++tt]=t-m;
if(x<n&&!st[t+m]&&a[t]>a[t+m])st[t+m]=1,q[++tt]=t+m;
if(x==n)c++;
}
if(c!=m){
printf("0\n%d",m-c);
return 0;
}
hh=t,tt=t-1;
for(int i=1;i<=t;++i)st[i]=0;
for(int i=1;i<=m;++i){
int w=(n-1)*m+i;
q[++tt]=w,e[w].l=e[w].r=i;
}
while(hh<=tt){
int t=q[hh],x=(t-1)/m+1,y=(t-1)%m+1;
++hh;
if(y>1&&!st[t-1]&&a[t]<a[t-1])st[t-1]=1,e[t-1].l=e[t].l,q[--hh]=t-1;
if(y<m&&!st[t+1]&&a[t]<a[t+1])st[t+1]=1,e[t+1].l=e[t].l,q[--hh]=t+1;
if(x>1&&!st[t-m]&&a[t]<a[t-m])st[t-m]=1,e[t-m].l=e[t].l,q[--hh]=t-m;
if(x<n&&!st[t+m]&&a[t]<a[t+m])st[t+m]=1,e[t+m].l=e[t].l,q[--hh]=t+m;
}
hh=t,tt=t-1;
for(int i=1;i<=t;++i)st[i]=0;
for(int i=m;i>=1;--i){
int w=(n-1)*m+i;
q[++tt]=w;
}
while(hh<=tt){
int t=q[hh],x=(t-1)/m+1,y=(t-1)%m+1;
++hh;
if(y>1&&!st[t-1]&&a[t]<a[t-1])st[t-1]=1,e[t-1].r=e[t].r,q[--hh]=t-1;
if(y<m&&!st[t+1]&&a[t]<a[t+1])st[t+1]=1,e[t+1].r=e[t].r,q[--hh]=t+1;
if(x>1&&!st[t-m]&&a[t]<a[t-m])st[t-m]=1,e[t-m].r=e[t].r,q[--hh]=t-m;
if(x<n&&!st[t+m]&&a[t]<a[t+m])st[t+m]=1,e[t+m].r=e[t].r,q[--hh]=t+m;
}
sort(e+1,e+m+1,cmp);
int s=1,t=m;
int ans=0;
for(int i=1;i<=m;i++){
if(e[i].r<s)continue;
int j=i,x=i;
while(j<=n&&e[j].l<=s){
if(s<=e[j].r&&e[x].r<e[j].r)x=j;
j++;
}
ans++;
s=e[x].r;
i=j-1;
if(s>=t){
printf("1\n%d",ans);
return 0;
}
}
printf("1\n%d",ans);
}
数据输入
```cpp
10 10
517 626 565 502 512 551 622 557 518 621
515 498 463 456 507 504 452 598 450 454
432 537 522 410 504 403 412 418 432 541
477 462 397 492 385 375 436 355 467 478
356 417 345 307 313 342 317 335 304 365
334 395 274 364 344 314 307 329 334 264
240 209 233 223 243 241 254 270 240 257
182 228 282 195 204 152 268 258 279 232
205 232 198 142 167 195 106 226 212 246
85 189 159 84 161 109 150 130 183 51
数据输出
1
7