fork download
copy 
  1.  
  2.  
  3. // author : daohuyenchi
  4.  
  5.  
  6.  
  7. #include <bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. #define ull unsigned long long
  12. #define db double
  13. #define i32 int32_t  
  14. #define i64 int64_t 
  15. #define ll long long
  16. // 
  17. #define fi first
  18. #define se second
  19.  
  20.  
  21. //                                      #define int long long    // consider carefully
  22.  
  23.  
  24. //
  25. #define pii pair<int, int>
  26. #define pli pair<ll, int>
  27. #define pll pair<ll, ll>
  28. #define pil pair<int, ll> 
  29. #define PAIR make_pair 
  30. //                                      TIME IS LIMITED ...  
  31. #define  rep(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
  32. #define repd(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
  33. #define repv(v, H) for(auto &v: H)
  34. //                                      REFLECT ON THE PAST ...
  35. #define RESET(c, x) memset(c, x, sizeof(c))
  36. #define MASK(i) (1LL << (i))
  37. #define BIT(mask, i) (((mask) >> (i)) & 1LL)
  38. #define ONBIT(mask, i) ((mask) | (1LL << (i)))
  39. #define OFFBIT(mask, i) ((mask) &~ (1LL << (i)))
  40. #define COUNTBIT __builtin_popcountll
  41. //                                      30 / 1 / 2024 ? love is zero... start from zero 
  42. #define PB push_back
  43. #define EB emplace_back
  44. #define vi vector<int>
  45. #define vll vector<ll>
  46. #define lwb lower_bound
  47. #define upb upper_bound
  48. #define all(v) (v).begin(), (v).end()
  49. #define special(H) (H).resize(distance(H.begin(), unique(all(H))))
  50. //                                      
  51. #define sp ' ' 
  52. #define nl '\n'
  53. #define yes "YES"
  54. #define no "NO"
  55. #define Log2(n) (63 - __builtin_clzll(n))
  56. #define left __left__
  57. #define right __right__ 
  58.  
  59. //____________________________________________________________________
  60.  
  61.  
  62. template <class X, class Y> bool maximize(X &a, const Y &b) {
  63.     if(a < b) return a = b, true;
  64.     return false;
  65. }
  66.  
  67. template <class X, class Y> bool minimize(X &a, const Y &b) {
  68.     if(a > b) return a = b, true;
  69.     return false;
  70. }
  71.  
  72. const int MOD      = 1000000007;
  73. // const int MOD[2] = {1000000009, 998244353};
  74.  
  75. template<class X> void modmize(X &x, int cur_Mod = MOD) {
  76.     if(x >= cur_Mod) x -= cur_Mod;
  77.     if(x < 0) x += cur_Mod;
  78. }
  79.  
  80. template <class... T>
  81. void print(T&&... n) {
  82.     using exp = int[];
  83.     exp{0, (cerr << n << sp, 0)...};
  84.     cerr << endl;
  85. }
  86.  
  87. template <class T, class... C>
  88. void assign(int n, T v, C&&... a) {
  89.     using e = int[];
  90.     e{(a.assign(n, v), 0)...};
  91. }
  92.  
  93. template <class... C>
  94. void resize(int n, C&&... a) {
  95.     using e = int[];
  96.     e{(a.resize(n), 0)...};
  97. }
  98.  
  99. template <class T>
  100. using vector2d = vector<vector<T>>;
  101. template <class T>
  102. using vector3d = vector<vector2d<T>>;
  103.  
  104. template <class T> int ssize(T &a) { return (int) a.size(); }
  105.  
  106.  
  107. //____________________________________________________________________
  108.  
  109.  
  110. mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
  111.  
  112. const long long oo = 1e18 + 7;
  113. const int INF      = 2e9;
  114. const int nmax     = 2e5 + 10;
  115. const int MAX      = 2e5;
  116. const int base     = 311;
  117. const db eps       = 1e-6;
  118. const int block    = 500;
  119. static const double PI = acos(-1.0);
  120.  
  121. //____________________________________________________________________
  122.  
  123.  
  124. int n, m;
  125. vector2d<int> a;
  126. vector2d<int> fd, fu, fl, fr;
  127.  
  128. namespace subtask1 {
  129.  
  130.     struct HuyenChi {
  131.  
  132.         vector<int> st;
  133.  
  134.         void Init(int _n) {
  135.             assign(_n * 4 + 5, INF, st);
  136.         }
  137.  
  138.         void upd(int id, int l, int r, int i, int val) {
  139.             if(l > i || r < i) return;
  140.             if(l == r) {
  141.                 minimize(st[id], val);
  142.                 return;
  143.             }
  144.             int mid = (l + r) / 2;
  145.             upd(id * 2, l, mid, i, val);
  146.             upd(id * 2 + 1, mid + 1, r, i, val);
  147.             st[id] = min(st[id * 2], st[id * 2 + 1]);
  148.         }
  149.  
  150.         int walk(int id, int l, int r, int val) {
  151.             if(l == r) return (st[id] <= val ? l : INF);
  152.             int mid = (l + r) / 2;
  153.             if(st[id * 2 + 1] <= val) return walk(id * 2 + 1, mid + 1, r, val);
  154.             return walk(id * 2, l, mid, val);
  155.         }
  156.  
  157.         int calc(int id, int l, int r, int u, int v, int val) {
  158.             if(l > v || r < u || st[id] > val) return INF;
  159.             if(u <= l && r <= v) {
  160.                 if(st[id] <= val) return walk(id, l, r, val);
  161.                 else return INF;
  162.             }
  163.             int mid = (l + r) >> 1;
  164.             if(v <= mid) return calc(id * 2, l, mid, u, v, val);
  165.             else if(u > mid) return calc(id * 2 + 1, mid + 1, r, u, v, val);
  166.             int cur = calc(id * 2 + 1, mid + 1, r, u, v, val);
  167.             if(cur < INF) return cur;
  168.             return calc(id * 2, l, mid, u, v, val);
  169.         } 
  170.  
  171.     } ;
  172.  
  173.     void SOLVE() {
  174.  
  175.         HuyenChi chi;
  176.  
  177.         vector2d<pii> List(2 * m + 1, vector<pii>());
  178.  
  179.         rep(i, 1, n) {
  180.             rep(j, 1, m) {
  181.                 if(a[i][j] == 0) continue;
  182.                 List[i - j + m].push_back({i, j});
  183.             }
  184.         }
  185.  
  186.         int ans = 0;
  187.         rep(_i, 0, m + m) {
  188.             if(List[_i].empty() == 0) {
  189.                 chi.Init(n);
  190.  
  191.                 auto &g = List[_i];
  192.                 sort(all(List[_i]));
  193.  
  194.                 repd(i, ssize(g) - 1, 0) {
  195.                     int x = g[i].fi;
  196.                     int y = g[i].se;
  197.                     if(a[x][y] == 0) continue;
  198.  
  199.                     int v2 = min(fl[x][y], fu[x][y]);
  200.                     chi.upd(1, 1, n, x, x - v2);
  201.  
  202.                     int v = min(fr[x][y], fd[x][y]);
  203.                     int x2 = chi.calc(1, 1, n, x, x + v - 1, x - 1);
  204.                     if(x2 != INF) {
  205.                         maximize(ans, x2 - x + 1);
  206.  
  207.                     }
  208.  
  209.                 }
  210.             }
  211.         }
  212.  
  213.         cout << 1ll * ans * ans << nl;
  214.  
  215.     }
  216.  
  217. }
  218.  
  219. int rnd(int l, int r) {
  220.     return uniform_int_distribution<int> (l, r) (rng);
  221. }
  222.  
  223. void tintingyn() {
  224.  
  225.     cin >> n >> m;
  226.  
  227.     // n = 1e3; m = 1e3;
  228.  
  229.     assign(n + 2, vector<int>(m + 2, 0), a);
  230.     rep(i, 1, n) {
  231.         rep(j, 1, m) {
  232.             cin >> a[i][j];
  233.             // a[i][j] = rnd(0, 1);
  234.         }
  235.     }
  236.  
  237.     assign(n + 2, vector<int>(m + 2, 0), fd, fu, fl, fr);
  238.  
  239.     rep(i, 1, n) {
  240.         fl[i][1] = 1;
  241.         rep(j, 2, m) {
  242.             if(a[i][j] != a[i][j - 1]) fl[i][j] = 1;
  243.             else fl[i][j] = fl[i][j - 1] + 1;
  244.         }
  245.         fr[i][m] = 1;
  246.         repd(j, m - 1, 1) {
  247.             if(a[i][j] != a[i][j + 1]) fr[i][j] = 1;
  248.             else fr[i][j] = fr[i][j + 1] + 1;
  249.         }
  250.     }
  251.  
  252.     rep(j, 1, m) {
  253.         fu[1][j] = 1;
  254.         rep(i, 2, n) {
  255.             if(a[i][j] != a[i - 1][j]) fu[i][j] = 1;
  256.             else fu[i][j] = fu[i - 1][j] + 1;
  257.         }
  258.  
  259.         fd[n][j] = 1;
  260.         repd(i, n - 1, 1) {
  261.             if(a[i][j] != a[i + 1][j]) fd[i][j] = 1;
  262.             else fd[i][j] = fd[i + 1][j] + 1;
  263.         }
  264.     }
  265.  
  266.     subtask1:: SOLVE();
  267.  
  268.  
  269.  
  270. }
  271.  
  272. signed main() {
  273.     ios_base::sync_with_stdio(0);
  274.     cin.tie(0);
  275.     cout.tie(0);
  276.  
  277.     //________________________________________________________________
  278.  
  279.     #define TASK "MSQUARE"
  280.     if(fopen(TASK".inp", "r")) {
  281.         freopen(TASK".inp", "r", stdin);
  282.         freopen(TASK".out", "w", stdout);
  283.     }
  284.  
  285.     //________________________________________________________________
  286.  
  287.     //  CODE FROM HERE ...! 
  288.  
  289.  
  290.  
  291.  
  292.  
  293.     int num_test = 1; 
  294.     // cin >> num_test;
  295.  
  296.     while(num_test--) {
  297.  
  298.         tintingyn();
  299.  
  300.     }
  301.  
  302.  
  303.     cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" << nl;
  304.  
  305.     return 0;
  306. }
Success #stdin #stdout #stderr 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time elapsed: 0.007472 s
https://ideone.com/DWJTpF
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!