#include <bits/stdc++.h>
using namespace std;
template <class T> inline void read(T &x) {
x = 0; register char ch = getchar();
for (; ch<'0' || ch>'9';) ch = getchar();
for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
}
//~ #define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> inline void chmin(T& a, const T& b) {if(a>b)a=b;}
template<class T> inline void chmax(T& a, const T& b) {if(a<b)a=b;}
const int mod = 1e9+7, N = 1005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k;
int a[N][N];
struct segtree{
vector<int> t,lz;
int sz;
inline void init(int row){
sz=1;
while(sz < m)sz<<=1;
t.assign(sz<<1,-mod);
lz.assign(sz<<1,0);
for(int j=0;j<m;j++){
t[j+sz] = a[row][j] - j - 1;
}
for(int j=sz-1;j>0;j--){
t[j] = max(t[j<<1],t[j<<1|1]);
}
}
inline void push(int x){
if(lz[x] == 0)return;
t[x] += lz[x];
if(x < sz){
lz[x<<1] += lz[x];
lz[x<<1|1] += lz[x];
}lz[x] = 0;
return;
}
inline void update(int l, int r, int L, int R, int x, int val){
push(x);
if(R <= l || L >= r)return;
if(L >= l && R <= r){
lz[x] += val;
push(x);
return;
}int mid = (L+R)>>1;
update(l,r,L,mid,x<<1,val);
update(l,r,mid,R,x<<1|1,val);
t[x] = max(t[x<<1], t[x<<1|1]);
}
inline void chm(int pos, int val){
update(pos,pos+1,0,sz,1,0);
pos += sz;
for(chmax(t[pos],val);pos>1;pos>>=1)t[pos>>1] = max(t[pos],t[pos^1]);
return;
}
inline void update(int l, int r, int val){
update(l,r,0,sz,1,val);
return;
}
inline int get(){
return t[1];
}
};
inline void solve(int test_case){
int i, j;
read(n);read(m);
for(i=0;i<n;i++){
for(j=0;j<m;j++){
read(a[i][j]);
}
}
int ans = -2;
{
segtree seg;
seg.init(0);
for(i=0;i<n;i++){
if(i%2==0){
chmax(ans, seg.get() - a[i][0]);
for(j=1;j<m;j++){
seg.update(0,j,-1);
seg.update(j,m,1);
chmax(ans, seg.get()-a[i][j]);
}
seg.update(0,m,-1);
for(j=0;j<m;j++){
seg.chm(j,a[i+1][j]-(m-j-1)-1);
}
}else {
chmax(ans, seg.get() - a[i][m-1]);
for(j=m-1;j>=0;j--){
seg.update(0,j,1);
seg.update(j,m,-1);
chmax(ans, seg.get()-a[i][j]);
}
seg.update(0,m,-1);
for(j=0;j<m;j++){
seg.chm(j,a[i+1][j]-j-1);
}
}
}
}
for(int l=0,r=n-1;l<r;l++,r--){
for(j=0;j<m;j++){
swap(a[l][j],a[r][j]);
}
}
{
segtree seg;
seg.init(0);
for(i=0;i<n;i++){
if(i%2==0){
chmax(ans, seg.get() - a[i][0]);
for(j=1;j<m;j++){
seg.update(0,j,-1);
seg.update(j,m,1);
chmax(ans, seg.get()-a[i][j]);
}
seg.update(0,m,-1);
for(j=0;j<m;j++){
seg.chm(j,a[i+1][j]-(m-j-1)-1);
}
}else {
chmax(ans, seg.get() - a[i][m-1]);
for(j=m-1;j>=0;j--){
seg.update(0,j,1);
seg.update(j,m,-1);
chmax(ans, seg.get()-a[i][j]);
}
seg.update(0,m,-1);
for(j=0;j<m;j++){
seg.chm(j,a[i+1][j]-j-1);
}
}
}
}
cout << ans << '\n';
return;
}
/*
2 3
5 7 5
2 4 3
*/
signed main(){
//~ FASTIO;
//~ #define MULTITEST 1
#if MULTITEST
int _T;
cin >> _T;
for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
Compilation message
maxcomp.cpp: In function 'void read(T&)':
maxcomp.cpp:4:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
4 | x = 0; register char ch = getchar();
| ^~
maxcomp.cpp: In instantiation of 'void read(T&) [with T = int]':
maxcomp.cpp:76:8: required from here
maxcomp.cpp:4:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
364 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
