QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #411117 | #7051. Largest Common Submatrix | Liuhao | WA | 0ms | 3848kb | C++23 | 4.2kb | 2024-05-14 23:35:11 | 2024-05-14 23:35:12 |
Judging History
answer
//
// Created by liuhao on 2024/5/14.
//
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define endl '\n'
#define vii vector<vector<int>>
template<class Node>
struct SegmentTree {
#define mid ((l+r)/2)
int n;
std::vector<Node> node;
SegmentTree() : n(0) {}
SegmentTree(int n_, Node v_ = Node()) {
init(n_, v_);
}
template<class T>
SegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Node v_ = Node()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size()-1;
node.assign(4 << std::__lg(n+1), Node());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r == l)return void(node[p] = init_[l]);
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
pushup(p);
};
build(1, 0, n);
}
void pushup(int p) {
node[p] = node[2 * p] + node[2 * p + 1];
}
void upd(int p, int l, int r, int x, const Node &v) {
if (r == l)return void(node[p] = v);
if (x <= mid) upd(2 * p, l, mid, x, v);
else upd(2 * p + 1, mid + 1, r, x, v);
pushup(p);
}
void upd(int p, const Node &v) {
upd(1, 0, n, p, v);
}
Node que(int p, int l, int r, int x, int y) {
if (l > y || r < x)return Node();
if (l >= x && r <= y)return node[p];
return que(2 * p, l, mid, x, y) + que(2 * p + 1, mid + 1, r, x, y);
}
Node que(int l, int r) {
return que(1, 0, n, l, r);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F pred) {
if (l > y || r < x || !pred(node[p]))return -1;
if (r == l)return l;
int res = findFirst(2 * p, l, mid, x, y, pred);
if (res == -1)res = findFirst(2 * p + 1, mid + 1, r, x, y, pred);
return res;
}
template<class F>
int findFirst(int l, int r, F pred) {//区间第一个满足条件的数
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F pred) {
if (l > y || r < x || !pred(node[p]))return -1;
if (r == l)return l;
int res = findLast(2 * p + 1, mid + 1, r, x, y, pred);
if (res == -1) res = findLast(2 * p, l, mid, x, y, pred);
return res;
}
template<class F>
int findLast(int l, int r, F pred) {//区间最后一个不满足条件的数
return findLast(1, 0, n, l, r, pred);
}
};
const int inf = 1e18;
struct Node {
int minn=inf;
};
Node operator+(Node a, Node b) {
Node c;
c.minn=max(a.minn,b.minn);
return c;
}
signed main() {
#ifdef Liuhao
freopen("in.txt", "r", stdin);
#else
ios;
#endif
int n,m;
cin>>n>>m;
vector a(n+1,vector<int>(m+1));
vector b(n+1,vector<int>(m+1));
vector<int>c(n*m+1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin>>a[i][j];
c[a[i][j]]=(i-1)*m+j;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin>>b[i][j];
b[i][j]=c[b[i][j]];
}
}
vector l(n+1,vector<int>(m+1));
vector r(n+1,vector<int>(m+1));
vector down(n+1,vector<int>(m+1));
for(int i=1;i<=m;i++){
down[n][i]=1;
for(int j=n-1;j>=1;j--){
if(b[j+1][i]-b[j][i]==m)down[j][i]=down[j+1][i]+1;
else down[j][i]=1;
}
}
int ans=0;
for (int i = 1; i <= n; i++) {
l[i][1]=1;
for (int j = 2; j <= m; j++) {
if(b[i][j]-b[i][j-1]==1)l[i][j]=l[i][j-1]+1;
else l[i][j]=1;
}
r[i][m]=1;
for(int j=m-1;j>=1;j--){
if(b[i][j+1]-b[i][j]==1)r[i][j]=r[i][j+1]+1;
else r[i][j]=1;
}
}
for (int i = 1; i <= n; i++) {
SegmentTree<Node>seg(m+2);
seg.upd(0,{0});
seg.upd(m+1,{0});
for (int j = 1; j <= m; j++) seg.upd(j,{down[i][j]});
for(int j=1;j<=m;j++){
int l0=seg.findFirst(0,j,[&](Node x){
if(x.minn>=down[i][j])return 1;
return 0;
});
int r0=seg.findLast(j,m+1,[&](Node x){
if(x.minn>=down[i][j])return 1;
return 0;
});
l0=min(j-l0+1,l[i][j]);
r0=min(r0+1-j,r[i][j]);
l0=min((b[i][j]-1)%m+1,l0);
r0=min(m-((b[i][j]-1)%m+1)+1,r0);
ans=max(ans,(l0+r0-1)*down[i][j]);
}
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
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: 3632kb
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: 0
Accepted
time: 0ms
memory: 3848kb
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:
80
result:
ok 1 number(s): "80"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3548kb
input:
10 10 37 16 29 24 14 20 41 63 4 15 71 99 17 26 33 47 83 55 89 52 32 22 95 44 81 93 78 31 42 12 94 70 25 46 18 97 57 62 68 67 21 69 54 27 13 96 64 48 59 28 11 49 9 73 100 90 85 36 2 58 74 53 98 34 7 5 3 91 23 76 77 86 84 92 50 51 45 61 30 66 35 1 10 79 39 6 80 82 43 88 75 60 38 87 40 8 19 56 72 65 37...
output:
100
result:
wrong answer 1st numbers differ - expected: '80', found: '100'