welleyth

Day 4. Rectangle

Jul 28th, 2021
586
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. //#define int long long
  7. #define uint __int128
  8. #define mp make_pair
  9. #define left left_compile
  10. #define right right_compile
  11.  
  12. #pragma GCC optimize("O3")
  13. #pragma GCC optimize("unroll-loops")
  14.  
  15. const int INF = (int)1e18;
  16. const int md = 998244353;
  17. const int MAXN = (int)1e6 + 10;
  18. const int N = (int)2e5 + 111;
  19. const int debug = 0;
  20. const long double eps = 1e-7;
  21.  
  22. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  23.  
  24. void init(){
  25.  
  26.     return;
  27. }
  28.  
  29. vector<vector<int>> g;
  30. //vector<vector<int>> Ops;
  31. //vector<vector<int>> d;
  32. //vector<vector<int>> pref;
  33.  
  34. int sum(int x1,int y1,int x2,int y2){
  35.     return g[x2][y2] - g[x2][y1-1] - g[x1-1][y2] + g[x1-1][y1-1];
  36. }
  37.  
  38. const int DX[] = {0,-1};
  39. const int DY[] = {-1,0};
  40.  
  41. void solve_case(){
  42.     int n,m;
  43.     cin >> n >> m;
  44.  
  45.     g.resize(n+1,vector<int>(m+2,0));
  46.     //d.resize(n+1,vector<int>(m+1,INF));
  47.     //pref.resize(n+1,vector<int>(m+2,0));
  48.     //Ops.resize(n+1,vector<int>(m+2));
  49.  
  50.     int Q;
  51.     cin >> Q;
  52.     int x1,x2,y1,y2;
  53.     for(int t = 0; t < Q; t++){
  54.         cin >> x1 >> y1 >> x2 >> y2;
  55.         for(int i = x1; i <= x2; i++){
  56.             g[i][y1]++;
  57.             g[i][y2+1]--;
  58.         }
  59.     }
  60.  
  61.     int cnt;
  62.  
  63.     for(int i = 1; i <= n; i++){
  64.         cnt = 0;
  65.         for(int j = 1; j <= m; j++){
  66.             cnt += g[i][j];
  67.             g[i][j] = (cnt > 0);
  68.         }
  69.     }
  70.  
  71.     int x,y;
  72.  
  73.     for(int i = 1; i <= n; i++){
  74.         for(int j = 1; j <= m; j++){
  75.             g[i][j] = g[i-1][j] + g[i][j-1] - g[i-1][j-1] + g[i][j];
  76.         }
  77.     }
  78.  
  79.     int ans = 0;
  80.     bool found = false;
  81.     ans = 0;
  82.  
  83.     for(int i = 1; i <= n && !found; i++){
  84.         for(int j = 1; j <= m && !found; j++){
  85.             for(int k = ans + 1; i + k - 1 <= n && j + k - 1 <= m; k++){
  86.                 if(sum(i,j,i+k-1,j+k-1))
  87.                     break;
  88.                 ans = max(ans,k);
  89.             }
  90.         }
  91.     }
  92.  
  93. //    assert(found);
  94.  
  95.     cout << ans;
  96.  
  97.     return;
  98. }
  99.  
  100. signed main(){
  101.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  102. //    freopen("input.txt","r",stdin);
  103. //    freopen("output.txt","w",stdout);
  104.  
  105.     init();
  106.  
  107.     int tests = 1;
  108. //    cin >> tests;
  109.  
  110.     for(int _ = 1; _ <= tests; _++){
  111. //        n = _;
  112.         solve_case();
  113.     }
  114.  
  115.     return 0;
  116. }
  117.  
RAW Paste Data