Advertisement
Guest User

Untitled

a guest
Jul 17th, 2019
228
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.21 KB | None | 0 0
  1. // CS Academy - Junior Challenge 2017 - Counting Gigel Matrices
  2. // Lúcio Cardoso
  3.  
  4. // Solution:
  5.  
  6. // Let Left[i][j] be the smallest index L such that every number in line i
  7. // in the column interval [L, j] is equal to 1. Define Right[i][j], Up[i][j] and Down[i][j]
  8. // similarly.
  9.  
  10. // For a fixed diagonal with only 1s, take its top-right corner (a, b). We want to find the amount of
  11. // points (c, d) in the diagonal such that the square formed by (a, b) and (c, d) is special. For that,
  12. // the following conditions have to be met:
  13.  
  14. // 1. Right[a][b] >= d
  15. // 2. Down[a][b] >= c
  16. // 3. Left[c][d] <= b
  17. // 4. Up[c][d] <= a
  18.  
  19. // Conditions (1) and (2) are analogous to:
  20. // min(Right[a][b]-b, Down[a][b]-a) >= d-b <-> min(Right[a][b]-d, Down[a][b]-a)+b >= d. (5)
  21.  
  22. // Conditions (3) and (4) are analoogus to:
  23. // min(d-Left[c][d], c-Up[c][d]) >= d-b <-> min(d-Left[c][d], c-Up[c][d])-d >= -b (6).
  24.  
  25. // While walking in the diagonal, we can maintain a priority_queue with values from LHS of (6). Whenever
  26. // we're at corner (a, b) of the diagonal, we remove any value less than -b from the priority_queue.
  27.  
  28. // For all values that are in the priority queue, we can use a BIT on values of RHS of (5). That way,
  29. // we can query for the LHS of (5) in the BIT and get our answer.
  30.  
  31. // Complexity is O(n^2 log n).
  32.  
  33. #include <bits/stdc++.h>
  34.  
  35. using namespace std;
  36.  
  37. const int maxn = 2e3+5;
  38.  
  39. typedef pair<int, int> pii;
  40.  
  41. int n, m;
  42. int tab[maxn][maxn];
  43.  
  44. int Up[maxn][maxn], Down[maxn][maxn];
  45. int Left[maxn][maxn], Right[maxn][maxn];
  46.  
  47. int bit[maxn];
  48.  
  49. void upd(int x, int v)
  50. {
  51. for (; x < maxn; x += (x&-x))
  52. bit[x] += v;
  53. }
  54.  
  55. int soma(int x)
  56. {
  57. int ans = 0;
  58. for (; x > 0; x -= (x&-x))
  59. ans += bit[x];
  60.  
  61. return ans;
  62. }
  63.  
  64. void calc(void)
  65. {
  66. for (int i = 1; i <= n; i++)
  67. {
  68. for (int j = 1; j <= m; j++)
  69. {
  70. if (!tab[i][j]) continue;
  71.  
  72. Up[i][j] = (tab[i-1][j] ? Up[i-1][j] : i);
  73. Left[i][j] = (tab[i][j-1] ? Left[i][j-1] : j);
  74. }
  75. }
  76.  
  77. for (int i = n; i >= 1; i--)
  78. {
  79. for (int j = m; j >= 1; j--)
  80. {
  81. if (!tab[i][j]) continue;
  82.  
  83. Down[i][j] = (tab[i+1][j] ? Down[i+1][j] : i);
  84. Right[i][j] = (tab[i][j+1] ? Right[i][j+1] : j);
  85. }
  86. }
  87. }
  88.  
  89. priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
  90.  
  91. inline void remove(int a)
  92. {
  93. while (pq.size())
  94. {
  95. pair<int, pii> tp = pq.top();
  96.  
  97. int x = tp.second.first, y = tp.second.second;
  98. if (tp.first >= -a) break;
  99.  
  100. upd(x, -1);
  101.  
  102. pq.pop();
  103. }
  104. }
  105.  
  106. void add(int a, int b)
  107. {
  108. pq.push({min(a-Up[a][b], b-Left[a][b])-a, {a, b}});
  109.  
  110. upd(a, 1);
  111. }
  112.  
  113. int main(void)
  114. {
  115. scanf("%d %d", &n, &m);
  116.  
  117. for (int i = 1; i <= n; i++)
  118. {
  119. for (int j = 1; j <= m; j++)
  120. {
  121. char c;
  122. scanf(" %c", &c);
  123. tab[i][j] = (c == '1' ? 1 : 0);
  124. }
  125. }
  126.  
  127. calc();
  128.  
  129. long long ans = 0;
  130.  
  131. for (int j = 1; j <= m; j++)
  132. {
  133. int a = n, b = j;
  134.  
  135. while (a >= 1 && b >= 1)
  136. {
  137. if (!tab[a][b])
  138. {
  139. remove(0), a--, b--;
  140. continue;
  141. }
  142.  
  143. remove(a);
  144. add(a, b);
  145.  
  146. ans += 1ll*soma(min(Down[a][b]-a, Right[a][b]-b)+a);
  147. a--, b--;
  148. }
  149.  
  150. remove(0);
  151. }
  152.  
  153. for (int i = n-1; i >= 1; i--)
  154. {
  155. int a = i, b = m;
  156.  
  157. while (a >= 1 && b >= 1)
  158. {
  159. if (!tab[a][b])
  160. {
  161. remove(0), a--, b--;
  162. continue;
  163. }
  164.  
  165. remove(a);
  166. add(a, b);
  167.  
  168. ans += 1ll*soma(min(Down[a][b]-a, Right[a][b]-b)+a);
  169. a--, b--;
  170. }
  171.  
  172. remove(0);
  173. }
  174.  
  175. printf("%lld\n", ans);
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement