fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define ld long double
  7. #define bigint __int128
  8. #define emb emplace_back
  9. #define pb push_back
  10. #define pii pair <int, int>
  11. #define fi first
  12. #define se second
  13. #define all(v) v.begin(), v.end()
  14. #define Task ""
  15.  
  16. #define MASK(k) (1ull << k)
  17. #define bitcnt(k) __builtin_popcount(k)
  18. #define testBit(n, k) ((n >> k) & 1)
  19. #define flipBit(n, k) (n ^ (1ll << k))
  20. #define offBit(n, k) (n & ~MASK(k))
  21. #define onBit(n, k) (n | (1ll << k))
  22.  
  23. template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
  24. template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}
  25.  
  26. const int N = 5e3 + 5, lim = 60, mod = 1e9 + 7;
  27. const ll INF = 1e18;
  28.  
  29. int n, q;
  30. char a[N][N];
  31.  
  32. int h[N], l[N], r[N];
  33. ll get_ans() {
  34. 	ll ans = 0;
  35. 	for (int i = 1; i <= n; i++) h[i] = 0;
  36. 	for (int i = 1; i <= n; i++) {
  37. 		for (int j = 1; j <= n; j++)
  38. 			h[j] = (a[i][j] == '0' ? h[j] + 1 : 0);
  39.  
  40. 		stack <int> st;
  41. 		for (int j = 1; j <= n; j++) {
  42. 			while (!st.empty() && h[st.top()] >= h[j]) st.pop();
  43. 			l[j] = (st.empty() ? 0 : st.top()) + 1;
  44. 			st.emplace(j);
  45. 		}
  46.  
  47. 		while (!st.empty()) st.pop();
  48. 		for (int j = n; j > 0; j--) {
  49. 			while (!st.empty() && h[st.top()] > h[j]) st.pop();
  50. 			r[j] = (st.empty() ? n + 1 : st.top()) - 1;
  51. 			st.emplace(j);
  52. 		}
  53.  
  54. 		for (int i = 1; i <= n; i++)
  55. 			ans += 1ll * (i - l[i] + 1) * (r[i] - i + 1) * h[i];
  56. 	}
  57. 	return ans;
  58. }
  59.  
  60. namespace sub3 {
  61. 	void solve() {
  62. 		cout << get_ans() << '\n';
  63. 		while (q--) {
  64. 			int x, y; cin >> x >> y;
  65. 			a[x][y] ^= 1;
  66. 			cout << get_ans() << '\n';
  67. 		}
  68. 	}
  69. }
  70.  
  71. namespace sub5 {
  72. 	short up[N][N], dw[N][N];
  73. 	ll curAns;
  74.  
  75. 	void update(int r, int c) {
  76. 		up[c][r] = 0;
  77. 		for (int i = r; i <= n; i++) {
  78. 			up[c][i] = (a[i][c] == '1' ? i : up[c][i - 1]);
  79. 		}
  80. 		dw[c][n + 1] = n + 1;
  81. 		for (int i = r; i > 0; i--) {
  82. 			dw[c][i] = (a[i][c] == '1' ? i : dw[c][i + 1]);
  83. 		}
  84. 	}
  85.  
  86. 	void preProcess() {
  87. 		for (int c = 1; c <= n; c++) {
  88. 			update(1, c);
  89. 			update(n, c);
  90. 		}
  91. 		curAns = get_ans();
  92. 	}
  93.  
  94. 	int u[N], d[N];
  95. 	ll get(int x, int y) {
  96. 		u[y] = x - up[y][x]; d[y] = dw[y][x] - x;
  97.  
  98. 		int L = y, R = y;
  99. 		while (L > 1 && a[x][L - 1] == '0') --L;
  100. 		while (R < n && a[x][R + 1] == '0') ++R;
  101.  
  102. 		for (int i = y + 1; i <= R; i++) {
  103. 			u[i] = min(u[i - 1], x - up[i][x]);
  104. 			d[i] = min(d[i - 1], dw[i][x] - x);
  105. 		}
  106. 		for (int i = y - 1; i >= L; i--) {
  107. 			u[i] = min(u[i + 1], x - up[i][x]);
  108. 			d[i] = min(d[i + 1], dw[i][x] - x);
  109. 		}
  110.  
  111. 		// min(u[l], u[r]) * min(d[l], d[r])
  112.  
  113. 		ll res = 0; int sumX = 0, sumY = 0;
  114. 		for (int l = y, r_u = y - 1, r_d = y - 1; l >= L; l--) { 
  115. 			// u[l] <= u[r]:
  116. 			// d[l] <= d[r], d[l] > d[r]
  117. 			while (r_u < R && u[l] <= u[r_u + 1]) sumX += d[++r_u];
  118. 			while (r_d < r_u && d[l] <= d[r_d + 1]) sumY += d[++r_d];
  119. 			res += 1ll * u[l] * d[l] * (r_d - y + 1);
  120. 			res += 1ll * u[l] * (sumX - sumY);
  121. 		}
  122.  
  123. 		sumX = sumY = 0;
  124. 		for (int r = y, l_u = y + 1, l_d = y + 1; r <= R; r++) {
  125. 			// u[r] < u[l]:
  126. 			// d[r] <= d[l], d[r] > d[l]
  127. 			while (l_u > L && u[r] < u[l_u - 1]) sumX += d[--l_u];
  128. 			while (l_d > l_u && d[r] <= d[l_d - 1]) sumY += d[--l_d];
  129. 			res += 1ll * u[r] * d[r] * (y - l_d + 1);
  130. 			res += 1ll * u[r] * (sumX - sumY);
  131. 		}
  132.  
  133. 		return res;
  134. 	}
  135.  
  136. 	void solve() {
  137. 		preProcess();
  138. 		cout << curAns << '\n';
  139.  
  140. 		while (q--) {
  141. 			int x, y; cin >> x >> y;
  142. 			if (a[x][y] == '1') {
  143. 				a[x][y] = '0'; update(x, y);
  144. 				curAns += get(x, y);
  145. 			}
  146. 			else {
  147. 				curAns -= get(x, y);
  148. 				a[x][y] = '1'; update(x, y);
  149. 			}
  150. 			cout << curAns << '\n';
  151. 		}
  152. 	}
  153. }
  154.  
  155. int main() {
  156. 	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  157.  
  158. 	if (fopen(Task".inp", "r")) {
  159. 		freopen(Task".inp", "r", stdin);
  160. 		freopen(Task".out", "w", stdout);
  161. 	}
  162.  
  163. 	cin >> n >> q;
  164. 	for (int i = 1; i <= n; i++)
  165. 		for (int j = 1; j <= n; j++)
  166. 			cin >> a[i][j];
  167.  
  168. 	sub5::solve();
  169. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/25UndK
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!