NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#148723	#1445. 理想的正方形	q779	100	823ms	41124kb	C++11	2.1kb	2022-07-17 18:27:15	2022-07-17 22:01:13

answer

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)

int k,n,m,st,en,q[N],mp[N][N];
int a[N][N],b[N][N],mx[N][N],mn[N][N];
void solve1(int *t,int rowid,int len,int f)
{
    st=en=0;
    for(int i=1; i<=len; i++)
    {
        if(f==1)while(st<en&&t[q[en]]<t[i])--en;
        if(f==2)while(st<en&&t[q[en]]>t[i])--en;
        q[++en]=i;
        while(st<en&&q[st+1]+k<=i)++st;
        if(i>=k)
        {
            if(f==1)a[i-k+1][rowid]=t[q[st+1]];
            if(f==2)b[i-k+1][rowid]=t[q[st+1]];
        }
    }
}
void solve2(int *t,int rowid,int len,int f)
{
    st=en=0;
    for(int i=1; i<=len; i++)
    {
        if(f==1)while(st<en&&t[q[en]]<t[i])--en;
        if(f==2)while(st<en&&t[q[en]]>t[i])--en;
        q[++en]=i;
        while(st<en&&q[st+1]+k<=i)++st;
        if(i>=k)
        {
            if(f==1)mx[i-k+1][rowid]=t[q[st+1]];
            if(f==2)mn[i-k+1][rowid]=t[q[st+1]];
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> mp[i][j];
    for(int i=1; i<=n; i++)
        solve1(mp[i],i,m,1),solve1(mp[i],i,m,2);
    for(int i=1; i<=m-k+1; i++)
        solve2(a[i],i,n,1),solve2(b[i],i,n,2);

    // cout << "------------------------\n";
    // for(int i=1; i<=m-k+1; i++)
    // {
    //     for(int j=1; j<=n; j++)
    //         cout << b[i][j] << " \n"[j==n];
    // }
    // for(int i=1; i<=n-k+1; i++)
    //     for(int j=1; j<=m-k+1; j++)
    //         cout << mx[i][j] << " \n"[j==m-k+1];
    int res=INF;
    for(int i=1; i<=n-k+1; i++)
        for(int j=1; j<=m-k+1; j++)
            res=min(res,mx[i][j]-mn[i][j]);
    cout << res << '\n';
    return 0;
}

源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10

Accepted

time: 162ms

memory: 40492kb

input:

1000 1000 100
804544523 340648618 718292412 235345736 704741136 942776831 741228920 463473302 677289...

output:

998893495

result:

ok single line: '998893495'

Test #2:

score: 10

Accepted

time: 179ms

memory: 40496kb

input:

1000 1000 100
629053044 957239666 456746076 940194386 201529807 592062148 244394389 825620014 223976...

output:

998862873

result:

ok single line: '998862873'

Test #3:

score: 10

Accepted

time: 0ms

memory: 9468kb

input:

output:

result:

ok single line: '2'

Test #4:

score: 10

Accepted

time: 0ms

memory: 18092kb

input:

100 100 10
2 100001 200001 300001 400001 500001 600001 700001 800001 900001 1000001 1100001 1200001 ...

output:

result:

ok single line: '908999'

Test #5:

score: 10

Accepted

time: 161ms

memory: 41124kb

input:

1000 1000 20
1 100001 200001 300001 400001 500001 600001 700001 800001 900001 1000001 1100001 120000...

output:

result:

ok single line: '1901899'

Test #6:

score: 10

Accepted

time: 38ms

memory: 28508kb

input:

500 500 50
79289095 232165705 955620938 481434262 465576217 112035388 50089892 459799006 181906335 3...

output:

995944328

result:

ok single line: '995944328'

Test #7:

score: 10

Accepted

time: 69ms

memory: 30472kb

input:

500 1000 80
499163842 331022295 940054497 684192083 248823911 842132608 629298697 398526298 98438040...

output:

998299092

result:

ok single line: '998299092'

Test #8:

score: 10

Accepted

time: 117ms

memory: 40648kb

input:

1000 1000 80
102 134 429 251 299 109 264 669 727 296 112 550 270 270 544 660 131 546 968 219 113 678...

output:

result:

ok single line: '998'

Test #9:

score: 10

Accepted

time: 33ms

memory: 27560kb

input:

500 500 100
65532583 920409544 753795976 989349545 818384831 778207112 425141881 853270293 542112588...

output:

999172505

result:

ok single line: '999172505'

Test #10:

score: 10

Accepted

time: 64ms

memory: 30156kb

input:

500 1000 100
456896744 779471086 578349238 52507342 192194992 156396237 475084995 775765435 96617474...

output:

998801667

result:

ok single line: '998801667'