Advertisement
Ahmed_Negm

Untitled

Apr 22nd, 2023
1,200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. #define ll long long
  7. #define OO 2'000'000'000
  8. #define ull unsigned long long
  9. #define nl '\n'
  10. #define sz(x) (ll)(x.size())
  11. #define all(x) x.begin(),x.end()
  12. #define rall(s)  s.rbegin(), s.rend()
  13. #define getline(s) getline(cin>>ws,s)
  14. #define ceill(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))
  15. #define pi  3.141592653589793
  16. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  17. #define multi_ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
  18.  
  19.  
  20. void Fast_IO(){
  21. ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  22. // freopen("filename.in", "r", stdin);
  23. // freopen("filename.txt", "w", stdout);
  24. #ifndef ONLINE_JUDGE
  25. freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  26. #endif
  27. }
  28.  
  29.  
  30.  
  31.  
  32. int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
  33. int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
  34.  
  35.  
  36. int n,m,q;
  37.  
  38. bool good(int sz , vector<vector<int>>&pre){
  39.     for(int i=1;i+sz-1<=n;i++){
  40.         for(int j=1;j+sz-1<=m;j++){
  41.             int sum =0;
  42.             if(i+sz-1<=n && j+sz-1<=m) sum += pre[i+sz-1][j+sz-1];
  43.             if(i-1>=1) sum -= pre[i-1][j+sz-1];
  44.             if(j-1>=1) sum -= pre[i+sz-1][j-1];
  45.             if(i-1>=1 && j-1>=1) sum += pre[i-1][j-1];
  46.             if(sum == 0) return true;
  47.         }
  48.     }
  49.     return false;
  50. }
  51.  
  52.  
  53.  
  54. void solve(){
  55. cin>>n>>m>>q;
  56. int maxi = max(n,m);
  57. vector<vector<int>>v(maxi+5,vector<int>(maxi+5));
  58.  
  59. auto fill =[&](int x1,int y1,int x2,int y2){
  60.     v[x2][y2]++,v[x2][y1-1]--;
  61.     v[x1-1][y2]--,v[x1-1][y1-1]++;
  62. };
  63.  
  64. auto build = [&](){
  65.     for(int i=n;i>=1;i--){
  66.         for(int j=m;j>=1;j--){
  67.             v[i][j] += v[i+1][j]+v[i][j+1]-v[i+1][j+1];
  68.         }
  69.     }
  70. };
  71.  
  72.  
  73. while(q--){
  74.     int x,y,k;
  75.     cin>>x>>y>>k;
  76.     int l = max(1,x-k),r = min(n,x+k);
  77.     int u = max(1,y-k),d = min(m,y+k);
  78.     // cout<<l<<" "<<r<<" "<<u<<" "<<d<<nl;
  79.     fill(x,l,x,r);
  80.     fill(u,y,d,y);
  81. }
  82.  
  83. build();
  84.  
  85. for(int i=1;i<=n;i++){
  86.     for(int j=1;j<=m;j++){
  87.         v[i][j] = min(v[i][j],1);
  88.     }
  89. }
  90.  
  91. vector<vector<int>>pre = v;
  92.  
  93. for(int i=1;i<=n;i++){
  94.     for(int j=1;j<=m;j++){
  95.         pre[i][j] += pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
  96.     }
  97. }
  98.  
  99.  
  100. int l=1,r=min(n,m),ans=-1;
  101.  
  102. while(l<=r){
  103.     int mid = l+(r-l)/2;
  104.     if(good(mid,pre)){
  105.         ans = mid;
  106.         l = mid+1;
  107.     }else{
  108.         r = mid-1;
  109.     }
  110. }
  111.  
  112. for(int i=1;i<=n;i++){
  113.     for(int j=1;j<=m;j++){
  114.         cout<<v[i][j]<<" ";
  115.     }
  116.     cout<<nl;
  117. }
  118.  
  119. if(ans == -1) cout<<-1<<nl;
  120. else cout<<ans*ans<<nl;
  121.  
  122.  
  123.  
  124.  
  125.  
  126. }
  127.  
  128. int main(){
  129.     Fast_IO();
  130. int t =1;
  131. //cin>>t;
  132. while(t--){
  133. solve();
  134. }
  135. return 0;
  136. }  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement