QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #521813 | #7051. Largest Common Submatrix | Symmetree | WA | 1ms | 12168kb | C++14 | 3.0kb | 2024-08-16 15:18:50 | 2024-08-16 15:18:51 |
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)
#define mid (l + r >> 1)
struct yjx{
int tre[N << 2];
void build(int k,int l,int r,int w){
if(l == r){
tre[k] = ly[w][l];
return;
}
build(k << 1,l,mid,w);
build(k << 1 | 1,mid + 1,r,w);
tre[k] = min(tre[k << 1],tre[k << 1 | 1]);
}
int query(int k,int l,int r,int x,int y){
if(x <= l && r <= y){
return tre[k];
}
int ret = 1e9;
if(x <= mid) ret = query(k << 1,l,mid,x,y);
if(y > mid) ret = min(ret,query(k << 1 | 1,mid + 1,r,x,y));
return ret;
}
}str;
vector<int> st[N];
int main(){
int i,j,k,x,y;
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 < st[j].size() - 1; ++i) {
tt = 0;
for(int x = st[j][i]; x < st[j][i + 1]; ++x) {
while(tt && lx[s[tt]][j] >= lx[x][j]) --tt;
res = max(res, (x - s[tt]) * (lx[x][j] - j + 1));
s[++tt] = x;
}
}
}
// int res = 0;
// for(i = 1;i <= n;i++){
// for(j = 1;j <= m;j++){
// x = str.query(1,1,m,j,lx[i][j]);
// //printf("%d %d\n",lst,x);
// res = max(res,(x - i + 1) * (lx[i][j] - j + 1));
// }
// }
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12084kb
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: 1ms
memory: 12168kb
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: 1ms
memory: 12124kb
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'