Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // CS Academy - Junior Challenge 2017 - Counting Gigel Matrices
- // Lúcio Cardoso
- // Solution:
- // Let Left[i][j] be the smallest index L such that every number in line i
- // in the column interval [L, j] is equal to 1. Define Right[i][j], Up[i][j] and Down[i][j]
- // similarly.
- // For a fixed diagonal with only 1s, take its top-right corner (a, b). We want to find the amount of
- // points (c, d) in the diagonal such that the square formed by (a, b) and (c, d) is special. For that,
- // the following conditions have to be met:
- // 1. Right[a][b] >= d
- // 2. Down[a][b] >= c
- // 3. Left[c][d] <= b
- // 4. Up[c][d] <= a
- // Conditions (1) and (2) are analogous to:
- // min(Right[a][b]-b, Down[a][b]-a) >= d-b <-> min(Right[a][b]-d, Down[a][b]-a)+b >= d. (5)
- // Conditions (3) and (4) are analoogus to:
- // min(d-Left[c][d], c-Up[c][d]) >= d-b <-> min(d-Left[c][d], c-Up[c][d])-d >= -b (6).
- // While walking in the diagonal, we can maintain a priority_queue with values from LHS of (6). Whenever
- // we're at corner (a, b) of the diagonal, we remove any value less than -b from the priority_queue.
- // For all values that are in the priority queue, we can use a BIT on values of RHS of (5). That way,
- // we can query for the LHS of (5) in the BIT and get our answer.
- // Complexity is O(n^2 log n).
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 2e3+5;
- typedef pair<int, int> pii;
- int n, m;
- int tab[maxn][maxn];
- int Up[maxn][maxn], Down[maxn][maxn];
- int Left[maxn][maxn], Right[maxn][maxn];
- int bit[maxn];
- void upd(int x, int v)
- {
- for (; x < maxn; x += (x&-x))
- bit[x] += v;
- }
- int soma(int x)
- {
- int ans = 0;
- for (; x > 0; x -= (x&-x))
- ans += bit[x];
- return ans;
- }
- void calc(void)
- {
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- {
- if (!tab[i][j]) continue;
- Up[i][j] = (tab[i-1][j] ? Up[i-1][j] : i);
- Left[i][j] = (tab[i][j-1] ? Left[i][j-1] : j);
- }
- }
- for (int i = n; i >= 1; i--)
- {
- for (int j = m; j >= 1; j--)
- {
- if (!tab[i][j]) continue;
- Down[i][j] = (tab[i+1][j] ? Down[i+1][j] : i);
- Right[i][j] = (tab[i][j+1] ? Right[i][j+1] : j);
- }
- }
- }
- priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
- inline void remove(int a)
- {
- while (pq.size())
- {
- pair<int, pii> tp = pq.top();
- int x = tp.second.first, y = tp.second.second;
- if (tp.first >= -a) break;
- upd(x, -1);
- pq.pop();
- }
- }
- void add(int a, int b)
- {
- pq.push({min(a-Up[a][b], b-Left[a][b])-a, {a, b}});
- upd(a, 1);
- }
- int main(void)
- {
- scanf("%d %d", &n, &m);
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- {
- char c;
- scanf(" %c", &c);
- tab[i][j] = (c == '1' ? 1 : 0);
- }
- }
- calc();
- long long ans = 0;
- for (int j = 1; j <= m; j++)
- {
- int a = n, b = j;
- while (a >= 1 && b >= 1)
- {
- if (!tab[a][b])
- {
- remove(0), a--, b--;
- continue;
- }
- remove(a);
- add(a, b);
- ans += 1ll*soma(min(Down[a][b]-a, Right[a][b]-b)+a);
- a--, b--;
- }
- remove(0);
- }
- for (int i = n-1; i >= 1; i--)
- {
- int a = i, b = m;
- while (a >= 1 && b >= 1)
- {
- if (!tab[a][b])
- {
- remove(0), a--, b--;
- continue;
- }
- remove(a);
- add(a, b);
- ans += 1ll*soma(min(Down[a][b]-a, Right[a][b]-b)+a);
- a--, b--;
- }
- remove(0);
- }
- printf("%lld\n", ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement