fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "recs"
  33. /*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
  34.  
  35. const int MOD = 1e9 + 7;
  36. const int inf = 1e9 + 27092008;
  37. const ll INF = 1e18 + 27092008;
  38. const int N = 5000 + 5;
  39. int numRow, numCol, numOne, targetSum;
  40. int row[N], col[N];
  41. vector<int> comRow(1, 0), comCol(1, 0), point_on_row[N];
  42. int distLeft[N], distRight[N], distBot[N], distTop[N];
  43.  
  44. void init(void) {
  45.     cin >> numRow >> numCol >> numOne >> targetSum;
  46.     FOR(i, 1, numOne) cin >> row[i] >> col[i];
  47.     FOR(i, 1, numOne) comRow.pb(row[i]);
  48.     FOR(i, 1, numOne) comCol.pb(col[i]);
  49.     sort(all(comRow)); comRow.resize(unique(all(comRow)) - comRow.begin());
  50.     sort(all(comCol)); comCol.resize(unique(all(comCol)) - comCol.begin());
  51.     FOR(i, 1, numOne) row[i] = lower_bound(all(comRow), row[i]) - comRow.begin();
  52.     FOR(i, 1, numOne) col[i] = lower_bound(all(comCol), col[i]) - comCol.begin();
  53. }
  54.  
  55. void process(void) {
  56.     if (targetSum == 0) return void(cout << 1LL * numRow * (numRow + 1) / 2 * numCol * (numCol + 1) / 2);
  57.     FOR(i, 1, numOne) point_on_row[row[i]].pb(col[i]);
  58.  
  59.     int diffRow = (int)comRow.size() - 1, diffCol = (int)comCol.size() - 1;
  60.     comRow.pb(numRow + 1); comCol.pb(numCol + 1);
  61.  
  62.     FOR(i, 1, diffRow) distBot[i] = comRow[i] - comRow[i - 1];
  63.     FOR(i, 1, diffRow) distTop[i] = comRow[i + 1] - comRow[i];
  64.  
  65.     FOR(i, 1, diffCol) distLeft[i] = comCol[i] - comCol[i - 1];
  66.     FOR(i, 1, diffCol) distRight[i] = comCol[i + 1] - comCol[i];
  67.  
  68.     ll countBoard = 0;
  69.  
  70.     FOR(bot, 1, diffRow) {
  71.         vector<int> cntOne(diffCol + 5, 0), ansCol(diffCol + 5, 0), sumCol(diffCol + 5, 0);
  72.         ll mul_left_right = 0;
  73.  
  74.         FOR(top, bot, diffRow) {
  75.             for(int point : point_on_row[top]) {
  76.                 cntOne[point]++;
  77.                 FOR(right, point, diffCol) if (ansCol[right] <= point) {
  78.                     if (ansCol[right - 1] > ansCol[right]) {
  79.                         mul_left_right -= 1LL * comCol[ansCol[right]] * distRight[right];
  80.                         sumCol[right] = sumCol[right - 1] + cntOne[right];
  81.                         ansCol[right] = ansCol[right - 1];
  82.                         mul_left_right += 1LL * comCol[ansCol[right]] * distRight[right];
  83.                     } else sumCol[right]++;
  84.  
  85.                     if (ansCol[right] <= point) {
  86.                         while(sumCol[right] - cntOne[ansCol[right]] >= targetSum) {
  87.                             mul_left_right -= 1LL * comCol[ansCol[right]] * distRight[right];
  88.                             sumCol[right] -= cntOne[ansCol[right]++];
  89.                             mul_left_right += 1LL * comCol[ansCol[right]] * distRight[right];
  90.                         }
  91.                     }
  92.                 } else break;
  93.             }
  94.  
  95.             countBoard += 1LL * mul_left_right * distBot[bot] * distTop[top];
  96.         }
  97.     }
  98.  
  99.     cout << countBoard;
  100. }
  101.  
  102. int main() {
  103.     ios_base::sync_with_stdio(0);
  104.     cin.tie(0); cout.tie(0);
  105.     if (fopen(task".inp", "r")) {
  106.         freopen(task".inp", "r", stdin);
  107.         freopen(task".out", "w", stdout);
  108.     }
  109.     int tc = 1;
  110. //    cin >> tc;
  111.     while(tc--) {
  112.         init();
  113.         process();
  114.     }
  115.     return 0;
  116. }
  117.  
  118.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JpOnnA
language:
C++14 (gcc 8.3)
created:
14 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!