QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #521840 | #7051. Largest Common Submatrix | Symmetree | WA | 2ms | 12140kb | C++14 | 2.5kb | 2024-08-16 15:43:03 | 2024-08-16 15:43:04 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<functional>
#include<utility>
#include<cassert>
using namespace std;
inline int read(){
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * f;
}
const int N = 1011;
int n,m,a[N][N],b[N][N],pos[N * N],lx[N][N],ly[N][N], s[N], tt;
#define p(x,y) (x - 1) * (m) + (y)
vector<int> st[N];
int main(){
int i,j;
n = read(),m = read();
for(i = 1;i <= n;i++){
for(j = 1;j <= m;j++){
a[i][j] = read();
pos[a[i][j]] = p(i,j);
}
}
for(i = 1;i <= n;i++){
for(j = 1;j <= m;j++){
b[i][j] = read();
//y = pos[b[i][j]] % m,x = (pos[b[i][j]] - y) / m + 1;
b[i][j] = pos[b[i][j]] - j - (i - 1) * m;
}
}
for(i = 1;i <= n;i++){
lx[i][m] = m;
for(j = m - 1;j >= 1;j--){
if(b[i][j] == b[i][j + 1]) lx[i][j] = lx[i][j + 1];
else lx[i][j] = j;
//printf("%d? ",lx[i][j]);
}
//puts("");
}
for(j = 1;j <= m;j++){
ly[n][j] = n; st[j].push_back(n + 1);
for(i = n - 1;i >= 1;i--){
if(b[i][j] == b[i + 1][j]) ly[i][j] = ly[i + 1][j];
else ly[i][j] = i, st[j].push_back(i + 1);
//printf("%d! ",ly[i][j]);
}
if(st[j].back() != 1) st[j].push_back(1);
reverse(st[j].begin(), st[j].end());
// puts("");
// printf("%d: ", j);
// for(int x: st[j]) printf("%d ", x); puts("");
}
// for(int j = m; j; --j) {
// for(int i = 1; i <= n; ++i) printf("%d ", b[i][j]);
// puts("");
// } puts("");
// for(int j = m; j; --j) {
// for(int i = 1; i <= n; ++i) printf("%d ", lx[i][j]);
// puts("");
// } puts("");
// for(int j = m; j; --j) {
// for(int i = 1; i <= n; ++i) printf("%d ", ly[i][j]);
// puts("");
// } puts("");
int res = 0;
for(int j = 1; j <= m; ++j) {
for(int i = 0; i < (int)st[j].size() - 1; ++i) {
tt = 0;
//s[++tt] = st[j][i] - 1;
for(int x = st[j][i]; x < st[j][i + 1]; ++x) {
while(tt && lx[s[tt]][j] >= lx[x][j]) --tt;
// printf("--%d\n", tt);
if(tt) res = max(res, (x - s[tt]) * (lx[x][j] - j + 1));
else res = max(res, (x - st[j][i] + 1) * (lx[x][j] - j + 1));
s[++tt] = x;
}
}
}
printf("%d\n",res);
return 0;
}
/*
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
*/
/*
3 4
1 2 4 5
3 6 12 11
8 9 7 10
10 7 9 8
11 12 6 3
4 5 2 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12140kb
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: 12096kb
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: 12104kb
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'