fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int N = 5e3 + 5;
  12. int n;
  13. pair <int, int> a[N];
  14. ll r, c, k;
  15.  
  16. void nhap() {
  17.     cin >> r >> c >> n >> k;
  18.     FOR(i, 1, n) cin >> a[i].fi >> a[i].se;
  19. }
  20.  
  21. void giai() {
  22.     if (!k) {
  23.         cout << r * (r + 1) / 2 * c * (c + 1) / 2;
  24.         return;
  25.     }
  26.  
  27.     vector<int> xs, ys;
  28.     FOR(i, 1, n) {
  29.         xs.push_back(a[i].fi);
  30.         ys.push_back(a[i].se);
  31.     }
  32.  
  33.     sort(xs.begin(), xs.end());
  34.     xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
  35.     sort(ys.begin(), ys.end());
  36.     ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
  37.  
  38.     int H = xs.size(), W = ys.size();
  39.  
  40.     FOR(i, 1, n) {
  41.         a[i].fi = lower_bound(xs.begin(), xs.end(), a[i].fi) - xs.begin() + 1;
  42.         a[i].se = lower_bound(ys.begin(), ys.end(), a[i].se) - ys.begin() + 1;
  43.     }
  44.  
  45.     vector<vector<int>> Row(H + 1);
  46.     FOR(i, 1, n) Row[a[i].fi].push_back(a[i].se);
  47.  
  48.     vector<ll> Top(H + 1), Bot(H + 1);
  49.     FOR(i, 1, H) {
  50.         ll pre = (i == 1 ? 0 : xs[i-2]);
  51.         Top[i] = xs[i-1] - pre;
  52.     }
  53.     FOR(i, 1, H) {
  54.         ll nxt = (i == H ? r + 1 : xs[i]);
  55.         Bot[i] = nxt - xs[i-1];
  56.     }
  57.  
  58.     vector<ll> Left(W + 1), Right(W + 1), Pre(W + 1);
  59.     FOR(j, 1, W) {
  60.         ll pre = (j == 1 ? 0 : ys[j-2]);
  61.         Left[j] = ys[j-1] - pre;
  62.     }
  63.     FOR(j, 1, W) {
  64.         ll nxt = (j == W ? c + 1 : ys[j]);
  65.         Right[j] = nxt - ys[j-1];
  66.     }
  67.     Pre[0] = 0;
  68.     FOR(j, 1, W) Pre[j] = Pre[j-1] + Left[j];
  69.  
  70.     vector<int> cnt(W + 2, 0);
  71.     ll ans = 0;
  72.  
  73.     FOR(top, 1, H) {
  74.         cnt.assign(W + 2, 0);
  75.         for (int bottom = top; bottom <= H; ++bottom) {
  76.             for (int y : Row[bottom]) cnt[y]++;
  77.  
  78.             int L = 1;
  79.             int curSum = 0;
  80.             FOR(R, 1, W) {
  81.                 curSum += cnt[R];
  82.                 while (L <= R && curSum - cnt[L] >= k) {
  83.                     curSum -= cnt[L];
  84.                     ++L;
  85.                 }
  86.                 if (curSum >= k) {
  87.                     ll SumL = Pre[L];
  88.                     ll waysCols = SumL * Right[R];
  89.                     ll waysRows = Top[top] * Bot[bottom];
  90.                     ans += waysRows * waysCols;
  91.                 }
  92.             }
  93.         }
  94.     }
  95.  
  96.     cout << ans;
  97. }
  98.  
  99. int main() {
  100.     ios_base::sync_with_stdio(0);
  101.     cin.tie(0); cout.tie(0);
  102.  
  103.     #define name "recs"
  104.  
  105.     if (fopen(name".inp", "r")) {
  106.         freopen(name".inp", "r", stdin);
  107.         freopen(name".out", "w", stdout);
  108.     }
  109.  
  110.     nhap();
  111.     giai();
  112.  
  113.     return 0;
  114. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MiXi8O
language:
C++14 (clang 8.0)
created:
2 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!