QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #199867 | #7051. Largest Common Submatrix | lyzqs# | WA | 3ms | 16312kb | C++14 | 2.6kb | 2023-10-04 14:24:57 | 2023-10-04 14:24:57 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <bitset>
#include <cmath>
#include <queue>
using namespace std;
#define x first
#define y second
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double,double> PDD;
typedef pair<LD,int> PLDI;
typedef pair<LD,LD> PLDLD;
typedef pair<int,PII> PIII;
const int N = 1010,M=2*N,U=200000,P=13331,INF=1e9+10,mod=998244353;
const double PI=acos(-1);
int n,m;
int a[N][N],b[N][N];
PII pos1[N*N],pos2[N*N];
struct Node
{
int l,r;
int v;
}tr[N*N*4];
int len[N*N];
ULL row1[N][N],row2[N][N],col1[N][N],col2[N][N],p[N];
void pushup(int u)
{
tr[u].v=min(tr[u*2].v,tr[u*2+1].v);
}
void build(int u,int l,int r)
{
tr[u]={l,r,len[l]};
if(l==r) return;
int mid=l+r>>1;
build(u*2,l,mid),build(u*2+1,mid+1,r);
pushup(u);
}
int query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;
int mid=tr[u].l+tr[u].r>>1;
int res=INF;
if(l<=mid) res=min(res,query(u*2,l,r));
if(r>mid) res=min(res,query(u*2+1,l,r));
return res;
}
ULL get(ULL H[],int l,int r)
{
return H[r]-H[l-1]*p[r-l+1];
}
int main()
{
p[0]=1;
for(int i=1;i<N;i++) p[i]=p[i-1]*P;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
pos1[a[i][j]]={i,j};
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&b[i][j]);
pos2[b[i][j]]={i,j};
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
row1[i][j]=row1[i][j-1]*P+a[i][j];
for(int j=1;j<=m;j++)
row2[i][j]=row2[i][j-1]*P+b[i][j];
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
col1[i][j]=col1[i][j-1]*P+a[j][i];
for(int j=1;j<=n;j++)
col2[i][j]=col2[i][j-1]*P+b[j][i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int di=pos2[a[i][j]].x,dj=pos2[a[i][j]].y;
int l=1,r=min(n-i+1,n-di+1);
while(l<r)
{
int mid=l+r+1>>1;
if(get(col1[j],i,i+mid-1)==get(col2[dj],di,di+mid-1)) l=mid;
else r=mid-1;
}
len[(i-1)*m+j]=l;
}
build(1,1,n*m);
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int di=pos2[a[i][j]].x,dj=pos2[a[i][j]].y;
int l=1,r=min(n-j+1,n-dj+1);
while(l<r)
{
int mid=l+r+1>>1;
if(get(row1[i],j,j+mid-1)==get(row2[di],dj,dj+mid-1)) l=mid;
else r=mid-1;
}
int mx=query(1,(i-1)*n+j,(i-1)*n+j+l-1);
ans=max(ans,mx*l);
}
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 16188kb
input:
3 4 5 6 7 8 1 2 3 4 9 10 11 12 5 6 8 7 1 2 4 3 12 11 10 9
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 16308kb
input:
10 10 13 2 57 50 1 28 37 87 30 46 66 47 33 69 83 52 97 55 91 18 9 48 23 35 98 8 7 95 90 5 3 53 43 36 96 59 26 4 70 17 71 100 15 94 25 72 84 89 21 73 64 34 22 29 42 92 85 78 86 62 99 79 67 11 6 19 24 51 77 74 75 16 88 44 93 39 41 82 56 65 12 40 63 54 10 60 32 45 20 80 49 61 76 14 81 68 27 31 58 38 13...
output:
100
result:
ok 1 number(s): "100"
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 16312kb
input:
10 10 6 48 98 83 7 56 22 49 61 34 8 87 91 100 16 17 86 24 9 23 94 50 81 59 51 21 52 20 33 25 73 1 70 45 36 31 88 90 12 69 64 57 60 5 85 29 37 96 92 41 89 67 79 84 35 68 46 18 38 63 27 55 65 95 11 43 47 72 80 66 75 39 58 62 77 53 15 40 3 71 32 82 10 99 44 2 30 76 74 28 19 78 13 97 26 42 54 14 4 93 6 ...
output:
60
result:
wrong answer 1st numbers differ - expected: '80', found: '60'