fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int MAXN = 3000;
  5. int n, m, p, k;
  6. vector<int> vec[MAXN + 5];
  7. int s[MAXN + 5], t[MAXN + 5];
  8. int lst[MAXN + 5], nxt[MAXN + 5];
  9. signed main() {
  10. 	scanf("%lld%lld%lld%lld", &n, &m, &p, &k);
  11. 	for (int i = 1; i <= p; i ++) {
  12. 		int x, y; scanf("%lld%lld", &x, &y);
  13. 		vec[x].push_back(y);
  14. 	}
  15. 	int ans = 0;
  16. 	for (int u = n; u >= 1; u --) {
  17. 		for (auto d : vec[u]) s[d] ++;
  18. 		int sum = 0, cur = 0;
  19. 		for (int l = 1, r = 1; l <= m; l ++) {
  20.  
  21. 			while (r <= m && sum < k) sum += s[r], r ++;
  22.             if (sum < k) break;
  23. 			cur += m - r + 2;
  24. 			sum -= s[l];
  25. 		}
  26. 		for (int i = 1; i <= m; i ++) t[i] = s[i];
  27. 		for (int i = 0; i <= m + 1; i ++) lst[i] = i - 1, nxt[i] = i + 1;
  28. 		for (int i = 1; i <= m; i ++) {
  29. 			if (!s[i]) {
  30. 				nxt[lst[i]] = nxt[i];
  31. 				lst[nxt[i]] = lst[i];
  32. 			}
  33. 		}
  34. 		for (int d = n; d >= u; d --) {
  35. 			ans += cur;
  36. 			for (int i : vec[d]) {
  37. 				int sl = t[i], sr = 0;
  38. 				int l = i, r = nxt[i];
  39. 				while (r <= m && sl + sr < k) {
  40.                     sr += t[r];
  41. 					r = nxt[r];
  42. 				}
  43.  
  44. 				while (1) {
  45. 					if (sl + sr == k) cur -= (l - lst[l]) * (r - lst[r]);
  46. 					l = lst[l]; sl += t[l];
  47. 					if (sl > k || l == 0) break;
  48. 					while (sl + sr > k) {
  49.                         r = lst[r];
  50. 						sr -= t[r];
  51. 					}
  52. 				}
  53.  
  54. 				t[i] -- ;
  55. 				if (t[i] == 0) {
  56. 					nxt[lst[i]] = nxt[i];
  57. 					lst[nxt[i]] = lst[i];
  58. 				}
  59. 			}
  60. 		}
  61. 	}
  62. 	printf("%lld", ans);
  63. 	return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qUm1A8
language:
C++14 (gcc 8.3)
created:
11 hours 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!