fork download 
  1. #include <bits/stdc++.h>
  2. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  3. using namespace std;
  4.  
  5. const int maxn = 1e5 + 10;
  6. const int maxk = 55;
  7. const int MOD = 1e9 + 7;
  8. struct EVENT{
  9.     int x;
  10.     int y1;
  11.     int y2;
  12.     int type;
  13. };
  14. //Các sự kiện sweepline gồm tọa độ x, độ dài y1, y2, và kiểu sự kiện
  15. //đóng hay mở một đoạn thẳng
  16.  
  17. bool comp(EVENT& A, EVENT& B){
  18.     if (A.x == B.x) return A.type > B.type;
  19.     return A.x < B.x;
  20. }
  21. //Xử lý các sự kiện x trước
  22. vector<EVENT> events;
  23.  
  24.  
  25.  
  26. vector<int> tempY;
  27. int n, k, treesize;
  28. long long T[maxk+1][maxn << 3];
  29. int delta[maxn << 3];
  30. // T[j][nod]: Tổng chiều dài trong khoảng quản lý của nút nod bị phủ ÍT NHẤT j lần.
  31. // delta[nod]: Số lần toàn đoạn [l,r] bị phủ đang được quản lý bởi nod
  32. //maxn << 1 cho số lượng sự kiện tối đa có thể xảy ra (1 mở và 1 đóng)
  33. //maxn << 3 cho ước lượng segment tree trên toàn sự kiện
  34. //maxk+1 để tránh tràn mảng vì phải lấy T(k) - T(k+1)
  35.  
  36.  
  37.  
  38. void push_up(int nod, int l, int r){
  39.     int len = tempY[r+1] - tempY[l];
  40.     int d = delta[nod];
  41.  
  42.     if (d >= k+1){
  43.         up(j,1,k+1) T[j][nod] = len;
  44.         return;
  45.     }
  46.     // Ngay cả khi bỏ qua con, delta đã đủ >= k+1 lần → mọi ngưỡng đều đạt
  47.  
  48.     if (l == r){
  49.         up(j,1,k+1) T[j][nod] = (d >= j) ? len : 0;
  50.         return;
  51.     }
  52.     // leaf
  53.  
  54.  
  55.     up(j,1,k+1){
  56.         if (j <= d) T[j][nod] = len;
  57.         else{
  58.             int need = j - d;
  59.             // đã đóng góp được d lần thì cần đóng góp thêm j-d lần nữa
  60.             T[j][nod] = T[need][nod*2] + T[need][nod*2+1];
  61.         }
  62.     }
  63. }
  64. //Nếu "khoảng" [l, r] bị bao hoàn toàn thì lấy toàn bộ
  65. //Nếu "khoảng" [l, r] chỉ bị bao một phần và không phải nút lá thì cập nhật dựa theo con
  66. //Nếu "khoảng" lá không bị bao thì phải bằng 0
  67. //Chú ý: nếu không có điều kiện (l != r) thì segment tree có thể lấy T[nod*2] với nod*2 là chỉ số tràn ngoài phạm vi đã khai báo
  68. //Chú ý: delta không bao giờ đẩy xuống nút con
  69.  
  70.  
  71.  
  72. void update(int nod, int l, int r, int u, int v, int val){
  73.     if (r < u || l > v) return;
  74.     if (l >= u && r <= v){
  75.         delta[nod] += val;
  76.         push_up(nod, l, r);
  77.         return;
  78.     }
  79.     int mid = (l+r) >> 1;
  80.     update(nod*2, l, mid, u, v, val);
  81.     update(nod*2+1, mid+1, r, u, v, val);
  82.     push_up(nod, l, r);
  83. }
  84.  
  85. signed main(){
  86.     ios_base::sync_with_stdio(false);
  87.     cin.tie(0);
  88.     #define Task "A"
  89.     if (fopen(Task".inp", "r")){
  90.         freopen(Task".inp", "r", stdin);
  91.         freopen(Task".out", "w", stdout);
  92.     }
  93.  
  94.     cin >> n >> k;
  95.     up(i,1,n){
  96.         int x1, y1, x2, y2;
  97.         cin >> x1 >> y1 >> x2 >> y2;
  98.         tempY.push_back(y1);
  99.         tempY.push_back(y2);
  100.         events.push_back({x1, y1, y2, 1});
  101.         events.push_back({x2, y1, y2, -1});
  102.     }
  103.  
  104.     tempY.push_back(-MOD);
  105.     sort(tempY.begin(), tempY.end());
  106.     tempY.resize(unique(tempY.begin(), tempY.end()) - tempY.begin());
  107.     treesize = tempY.size()-1;
  108. //    tempY thêm phần tử -MOD để lấy lowerbound với chỉ số bắt đầu từ 1
  109. //    treesize = tempY.size()-1 vì phải bỏ qua phần tử -MOD;
  110.  
  111.  
  112.     sort(events.begin(), events.end(), comp);
  113.  
  114.     long long res = 0;
  115.     for (int i = 0; i < (int)(events.size()-1); i++){
  116.         int u = lower_bound(tempY.begin(), tempY.end(), events[i].y1) - tempY.begin();
  117.         int v = lower_bound(tempY.begin(), tempY.end(), events[i].y2) - tempY.begin();
  118.  
  119.  
  120.         update(1, 1, treesize-1, u, v-1, events[i].type);
  121.         // Đúng k lần = (>= k) - (>= k+1)
  122.         res += 1ll*(T[k][1] - T[k+1][1]) * 1ll*(events[i+1].x - events[i].x);
  123.  
  124. //        Segment tree quản lý các "khoảng" giữa tọa độ điểm này và tọa độ điểm kia
  125. //        có treesize tọa độ điểm thì có treesize-1 "khoảng"
  126. //        Tại mỗi nút chỉ số v quản lý khoảng [l, r], lấy kết quả nút nếu bị bao toàn bộ là tempY[r+1] - tempY[l]
  127. //        Do đó, mỗi lần lấy kết quả trong tọa độ [u, v] thì lấy kết quả trên "khoảng" [u, v-1] trên segment tree
  128.     }
  129.     cout << res;
  130. }
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138. /** Code Trâu **/
  139. //#include <bits/stdc++.h>
  140. //#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  141. //using namespace std;
  142. //
  143. //int n, k;
  144. //map<pair<int, int>, int> a;
  145. //// Lưu số lần bị phủ của từng ô vuông đơn vị 1x1
  146. //
  147. //signed main(){
  148. //    ios_base::sync_with_stdio(false);
  149. //    cin.tie(0);
  150. //    #define Task "A"
  151. //    if (fopen(Task".inp", "r")){
  152. //        freopen(Task".inp", "r", stdin);
  153. //        freopen(Task".out", "w", stdout);
  154. //    }
  155. //
  156. //    cin >> n >> k;
  157. //    up(i, 1, n){
  158. //        int x1, y1, x2, y2;
  159. //        cin >> x1 >> y1 >> x2 >> y2;
  160. //        // x từ x1 đến x2-1 đại diện cho các ô vuông trên trục X
  161. //        up(x, x1, x2-1){
  162. //            up(y, y1, y2-1){
  163. //                a[make_pair(x, y)]++;
  164. //            }
  165. //        }
  166. //    }
  167. //
  168. //    int cnt = 0;
  169. //    for (auto it : a){
  170. //        if (it.second == k) {
  171. //            cnt++;
  172. //        }
  173. //    }
  174. //    cout << cnt << "\n";
  175. //
  176. //
  177. ////    down(j,maxy,-maxy){
  178. ////        up(i,-maxx,maxx){
  179. ////            cout << a[make_pair(i, j)] << " ";
  180. ////        }
  181. ////        cout << "\n";
  182. ////    }
  183. //}
Success #stdin #stdout 0.01s 13900KB
comments (?)
stdin 
99 4
-73 18 -10 44
84 20 84 24
3 -96 27 -3
85 24 89 64
13 -82 91 13
-38 41 42 61
-14 31 46 93
-26 -27 62 80
-42 -77 63 88
53 -85 69 2
28 -27 89 40
-66 -3 -7 63
90 -72 90 32
-86 35 -15 98
43 57 43 58
87 -50 94 96
26 -45 40 19
42 13 68 75
-34 33 -23 48
-64 83 35 86
39 -82 52 -22
86 -10 90 57
97 38 99 55
-63 -38 70 11
58 69 90 80
-5 -41 46 61
-15 -31 -15 72
68 -1 75 73
91 61 94 88
75 -73 97 98
-50 74 84 93
-63 -96 12 -88
41 -20 87 23
68 41 90 89
-21 -17 12 68
55 -9 77 -6
71 -30 100 13
-2 -71 82 -33
6 -30 25 -5
-60 -97 -7 -31
-94 49 19 51
10 -52 32 19
-55 -17 -4 90
-94 -11 12 4
-98 -13 34 50
11 -10 66 16
12 82 81 87
-27 -5 5 47
-21 30 -10 39
-30 -22 56 58
-42 -89 -18 35
-2 -15 75 89
86 47 89 60
-84 56 -82 73
-44 33 -21 59
90 -29 96 55
87 9 89 99
-25 51 77 85
81 26 83 88
-17 62 31 99
32 -82 63 -78
45 -96 99 55
20 -90 37 -38
-10 67 92 92
62 -41 88 7
-74 -40 -51 58
-95 73 95 85
21 -4 48 69
-10 -77 94 4
53 -92 80 79
90 -18 90 27
-41 27 14 62
-71 12 85 100
-13 6 71 61
73 35 86 93
67 95 87 100
90 -39 96 -5
-5 -31 -3 27
-66 27 -21 87
75 11 96 63
77 -69 88 -52
11 87 62 95
13 -58 73 62
-24 -46 73 -18
-70 -87 -16 -53
-15 -17 -3 -10
62 -89 72 43
-14 64 92 73
-63 -9 93 71
-44 -27 55 74
-42 -58 100 -5
-27 -1 8 60
81 -74 86 -34
-72 -34 33 66
-8 97 80 99
-37 10 31 35
43 -23 74 63
-52 -70 1 14
-36 7 30 13
stdout 
1980
https://ideone.com/Lrs1zX
Area intersected by exactly k rectangles
language:
C++14 (gcc 8.3)
created:
19 days ago
visibility:
secret

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!