fork download 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 1e5 + 5;
  4. const int SN = 1 << 20;
  5. const int MAX = 4e7;
  6. int curnode = 0;
  7. int val[MAX];
  8. int lft[MAX];
  9. int rgt[MAX];
  10. int maxx = 0;
  11. int maxy = 0;
  12. int value;
  13. int ychild[2][SN];
  14. int query(int l , int r , int node , int ql , int qr){
  15.     if(l > qr || r < ql || node == -1){
  16.         return 0;
  17.     }
  18.     if(l >= ql && r <= qr){
  19.         return val[node];
  20.     }
  21.     int mid = (l + r) >> 1;
  22.     return query(l , mid , lft[node] , ql , qr) + query(mid + 1 , r , rgt[node] , ql , qr);
  23. }
  24. int queryx(int l , int r , int tnode , bool k , int x1 , int y1 , int x2 , int y2){
  25.     if(l > x2 || r < x1 || x1 > x2 || y1 > y2 || ychild[k][tnode] == -1){
  26.         return 0;
  27.     }
  28.     if(l >= x1 && r <= x2){
  29.         return query(1 , maxx , ychild[k][tnode] , y1 , y2);
  30.     }
  31.     int mid = (l + r) >> 1;
  32.     return queryx(l , mid , tnode + tnode , k , x1 , y1 , x2 , y2) + queryx(mid + 1 , r , tnode + tnode + 1 , k , x1 , y1 , x2 , y2);
  33. }
  34. void update(int l , int r , int node , int idx){
  35.     val[node] += value;
  36.     if(l < r){
  37.         int mid = (l + r) >> 1;
  38.         if(idx <= mid){
  39.             if(lft[node] == -1){
  40.                 lft[node] = ++curnode;
  41.                 lft[curnode] = -1;
  42.                 rgt[curnode] = -1;
  43.                 val[curnode] = 0;
  44.             }
  45.             update(l , mid , lft[node] , idx);
  46.         }
  47.         else{
  48.             if(rgt[node] == -1){
  49.                 rgt[node] = ++curnode;
  50.                 lft[curnode] = -1;
  51.                 rgt[curnode] = -1;
  52.                 val[curnode] = 0;
  53.             }
  54.             update(mid + 1 , r , rgt[node] , idx);
  55.         }
  56.     }
  57. }
  58. void update(int l , int r , int tnode , bool k , int idx , int idy){
  59.     if(ychild[k][tnode] == -1){
  60.         ychild[k][tnode] = ++curnode;
  61.         val[curnode] = 0;
  62.         lft[curnode] = -1;
  63.         rgt[curnode] = -1;
  64.     }
  65.     update(1 , maxx , ychild[k][tnode] , idy);
  66.     if(l < r){
  67.         int mid = (l + r) >> 1;
  68.         if(idx <= mid){
  69.             update(l , mid , tnode + tnode , k , idx , idy);
  70.         }
  71.         else{
  72.             update(mid + 1 , r , tnode + tnode + 1 , k , idx , idy);
  73.         }
  74.     }
  75. }
  76. int n , t;
  77. int x[N];
  78. int y[N];
  79. long long ans = 0;
  80. map < int , int > m1 , m2;
  81. void insert(int idx){
  82.     if(x[idx] == x[idx - 1]){//vertical line with same x
  83.         value = 1;
  84.         update(1 , maxy , 1 , 0 , m2[min(y[idx] , y[idx - 1]) + 1] , m1[x[idx]]);
  85.         value = -1;
  86.         update(1 , maxy , 1 , 0 , m2[max(y[idx] , y[idx - 1])] , m1[x[idx]]);
  87.     }
  88.     else{
  89.         value = 1;
  90.         update(1 , maxy , 1 , 1 , m2[y[idx]] , m1[min(x[idx] , x[idx - 1]) + 1]);
  91.         value = -1;
  92.         update(1 , maxy , 1 , 1 , m2[y[idx]] , m1[max(x[idx] , x[idx - 1])]);
  93.     }
  94. }
  95. int solve(int idx){
  96.     if(x[idx] == x[idx - 1]){
  97.         return queryx(1 , maxy , 1 , 1 , m2[min(y[idx] , y[idx - 1]) + 1] , m1[1] , m2[max(y[idx] , y[idx - 1]) - 1] , m1[x[idx]]);
  98.     }
  99.     else{
  100.         return queryx(1 , maxy , 1 , 0 , m2[1] , m1[min(x[idx] , x[idx - 1]) + 1] , m2[y[idx]] , m1[max(x[idx] , x[idx - 1]) - 1]);
  101.     }
  102. }
  103. int main(){
  104.     freopen("mowing.in" , "r" , stdin);
  105.     freopen("mowing.out" , "w" , stdout);
  106.     m1[1];
  107.     m2[1];
  108.     memset(ychild , -1 , sizeof(ychild));
  109.     scanf("%d %d" , &n , &t);
  110.     for(int i = 1 ; i <= n ; ++i){
  111.         scanf("%d %d" , x + i , y + i);
  112.         m1[x[i]];
  113.         m1[x[i] + 1];
  114.         m1[x[i] - 1];
  115.         m2[y[i]];
  116.         m2[y[i] + 1];
  117.         m2[y[i] - 1];
  118.     }
  119.     for(auto it : m1){
  120.         m1[it.first] = ++maxx;
  121.     }
  122.     for(auto it : m2){
  123.         m2[it.first] = ++maxy;
  124.     }
  125.     for(int i = 1 ; i <= n ; ++i){
  126.         if(i - t - 1 > 1){
  127.             insert(i - t - 1);
  128.         }
  129.         if(i > 1){
  130.             ans += solve(i);
  131.         }
  132.     }
  133.     printf("%lld\n" , ans);
  134. }
Success #stdin #stdout 0s 481152KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/mTAbv4
language:
C++14 (gcc 8.3)
created:
8 years 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!