fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define
  5.  
  6. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  7. #define ll long long
  8. #define ii pair <int , int>
  9. #define iii pair <int , ii>
  10. #define se second
  11. #define fi first
  12. #define all(v) (v).begin() , (v).end()
  13. #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
  14. #define bit(x,i) (((x) >> (i)) & 1LL)
  15. #define flip(x,i) ((x) ^ (1LL << (i)))
  16. #define ms(d,x) memset(d , x , sizeof(d))
  17. #define exist __exist
  18. #define ends __ends
  19. #define visit visited
  20. #define left __left
  21. #define right __right
  22. #define prev __prev
  23. #define next __next
  24. #define sitingfake 1
  25. #define orz 1
  26. //constant
  27.  
  28. const long long mod = 1e9 + 7;
  29. const long long linf = 4557430888798830399LL;
  30. const long long nlinf = -4485090715960753727LL;
  31. const int inf = 1061109567;
  32. const int ninf = -1044266559;
  33. const int dx[] = {0 , -1 , 0 , 1};
  34. const int dy[] = {-1 , 0 , 1 , 0};
  35.  
  36. template<typename T> bool maximize(T &a, const T &b)
  37. {
  38.     if(a < b) {a = b; return 1;}
  39.     return 0;
  40. }
  41.  
  42. template<typename T> bool minimize(T &a, const T &b)
  43. {
  44.     if(a > b) {a = b; return 1;}
  45.     return 0;
  46. }
  47.  
  48. void Plus(ll & a ,ll b)
  49. {
  50.     b %= mod;
  51.     a += b;
  52.     if(a < 0) a += mod;
  53.     a %= mod;
  54.     return;
  55. }
  56.  
  57. void Mul(ll & a, ll b)
  58. {
  59.     (a *= (b % mod)) %= mod;
  60.     return;
  61. }
  62.  
  63. //code
  64. const int maxn = 5055;
  65.  
  66. int r , c , n , k;
  67.  
  68. ii a[maxn];
  69. int st[4 * maxn] , lazy[4 * maxn];
  70. vector <int> P[maxn];
  71. ll id[maxn];
  72. int numy;
  73.  
  74. void Compress()
  75. {
  76.     vector <int> p;
  77.     for(int i = 1; i <= n; i++)
  78.     {
  79.         p.push_back(a[i].se);
  80.     }
  81.     Unique(p);
  82.     for(int i = 1; i <= n; i++)
  83.     {
  84.         a[i].se = lower_bound(all(p) , a[i].se) - p.begin() + 1;
  85.     }
  86.     numy = p.size();
  87.     for(int i = 1; i <= numy; i++)
  88.     {
  89.         id[i] = p[i - 1];
  90.     }
  91.     id[numy + 1] = c + 1;
  92. }
  93.  
  94. void Push(int i)
  95. {
  96.     if(lazy[i] != 0)
  97.     {
  98.         st[i * 2] += lazy[i];
  99.         st[i * 2 + 1] += lazy[i];
  100.         lazy[i * 2 + 1] += lazy[i];
  101.         lazy[i * 2] += lazy[i];
  102.         lazy[i] = 0;
  103.         return;
  104.     }
  105. }
  106. void up(int i , int l , int r , int u , int v)
  107. {
  108.     if(u > r || v < l) return;
  109.     if(u <= l && r <= v)
  110.     {
  111.         st[i]++;
  112.         lazy[i]++;
  113.         return;
  114.     }
  115.     Push(i);
  116.     int mid = (r + l) >> 1;
  117.     up(i * 2  , l , mid , u , v);
  118.     up(i * 2 + 1 , mid + 1 , r , u , v);
  119.     st[i] = max(st[i * 2] , st[i * 2 + 1]);
  120. }
  121.  
  122. ii walk(int i , int l , int r , int val)
  123. {
  124.     if(st[i] < val) return ii(-1 , -1);
  125.     if(l == r)
  126.     {
  127.         return ii(st[i] , l);
  128.     }
  129.     Push(i);
  130.     int mid = (r + l) >> 1;
  131.     if(st[i * 2] >= val) return walk(i * 2 , l , mid , val);
  132.     return walk(i * 2 + 1 , mid + 1 , r , val);
  133. }
  134.  
  135. int getPos(int i , int l ,int r ,int pos)
  136. {
  137.     if(l == r) return st[i];
  138.     int mid = (r + l) >> 1;
  139.     Push(i);
  140.     if(pos <= mid) return getPos(i * 2 , l , mid , pos);
  141.     return getPos(i * 2 + 1 , mid + 1 , r , pos);
  142. }
  143.  
  144. void reset()
  145. {
  146.     for(int i = 1; i <= 4 * (numy + 2); i++) st[i] = lazy[i] = 0;
  147. }
  148.  
  149. void debug()
  150. {
  151.     for(int i = 0; i <= c; i++)
  152.     {
  153.         cout << getPos(1 , 0 , c , i) << " ";
  154.     }
  155.     cout << endl;
  156. }
  157.  
  158. ll Compute(int start)
  159. {
  160.     reset();
  161.     ll goodpairs = (1ll * c * (c + 1)) / 2;
  162.  
  163.     //cout << goodpairs << endl;
  164.     ll sum = 0;
  165.  
  166.     for(int i = start; i <= r; i++)
  167.     {
  168.         for(int pos : P[i])
  169.         {
  170.             int orgVal = getPos(1 , 0 , numy , pos);
  171.             int curPos = pos;
  172.             int curVal = orgVal;
  173.             int lim = curVal + k - 1;
  174.             while(curVal <= lim && curPos <= numy)
  175.             {
  176.                 int target = curVal - k + 1;
  177.                 ii right = walk(1 , 0 , numy , curVal + 1);
  178.                 if(right.se == -1) right.se = numy + 1;
  179.                 if(target >= 0)
  180.                 {
  181.                     if(target == orgVal)
  182.                     {
  183.                         int left = walk(1 , 0 , numy , target).se;
  184.                         goodpairs -= (id[pos] - id[left]) * (id[right.se] - id[curPos]);
  185.                     }
  186.                     else
  187.                     {
  188.                         ii l1 = walk(1 , 0 , numy , target);
  189.                         if(l1.fi == target)
  190.                         {
  191.                             ii r1 = walk(1 , 0 , numy , target + 1);
  192.                             goodpairs -= (id[r1.se] - id[l1.se]) * (id[right.se] - id[curPos]);
  193.                         }
  194.                     }
  195.                 }
  196.                 if(right.fi == -1) break;
  197.                 curPos = right.se;
  198.                 curVal = right.fi;
  199.             }
  200.             up(1 , 0 , numy , pos , numy);
  201.         }
  202.         //debug();
  203.         sum += goodpairs;
  204.     }
  205.     return sum;
  206. }
  207. void solve(void)
  208. {
  209.     cin >> r >> c >> n >> k;
  210.     if(k == 0)
  211.     {
  212.         cout << ((1ll * r * (r + 1)) / 2) * ((1ll * c * (c + 1)) / 2);
  213.         return;
  214.     }
  215.     for(int i = 1; i <= n; i++)
  216.     {
  217.         cin >> a[i].fi >> a[i].se;
  218.     }
  219.     Compress();
  220.     for(int i = 1; i <= n; i++) P[a[i].fi].push_back(a[i].se);
  221.     for(int i = 1; i <= r; i++) sort(all(P[i]));
  222.     ll ans = 0;
  223.     for(int i = 1; i <= r; i++)
  224.     {
  225.         ans += Compute(i);
  226.     }
  227.     //cout << ans;
  228.     cout << ((1ll * r * (r + 1)) / 2) * ((1ll * c * (c + 1)) / 2) - ans;
  229. }
  230. /**
  231. .XXX.
  232. ..X..
  233. **/
  234. signed main()
  235. {
  236.    ios_base::sync_with_stdio(0);
  237.    cin.tie(0);
  238.    cout.tie(0);
  239.  
  240.    #define task "recs"
  241.  
  242.    if(fopen(task".inp","r"))
  243.    {
  244.        freopen(task".inp","r",stdin);
  245.        freopen(task".out","w",stdout);
  246.    }
  247.  
  248.    int tc = 1;
  249. //   cin >> tc;
  250.    while(tc--) solve();
  251.  
  252.    execute;
  253. }
  254.  
  255.  
  256.  
  257.  
Success #stdin #stdout #stderr 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
 Time: 0.004478s
https://ideone.com/RfSZnM
language:
C++14 (clang 8.0)
created:
3 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!