fork download
copy 
  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 MOD = 1e9 + 7;
  7. struct EVENT{
  8.     int x;
  9.     int y1;
  10.     int y2;
  11.     int type;
  12. };
  13. //Các sự kiện sweepline gồm tọa độ x, độ dài y1, y2, và kiểu sự kiện
  14. //đóng hay mở một đoạn thẳng
  15.  
  16. bool comp(EVENT& A, EVENT& B){
  17.     if (A.x == B.x) return A.type > B.type;
  18.     return A.x < B.x;
  19. }
  20. //Xử lý các sự kiện x trước
  21.  
  22. vector<EVENT> events;
  23. vector<int> tempY;
  24.  
  25. int n, treesize;
  26. long long T1[maxn << 3];
  27. long long T2[maxn << 3];
  28. long long T3[maxn << 3];
  29. int delta[maxn << 3];
  30. //maxn << 1 cho số lượng sự kiện tối đa có thể xảy ra (1 mở và 1 đóng)
  31. //maxn << 3 cho ước lượng segment tree trên toàn sự kiện
  32.  
  33. void push_up(int nod, int l, int r){
  34.     int len = tempY[r+1] - tempY[l];
  35.     if (delta[nod] >= 3) {
  36. //      đoạn này bị phủ >=3 lần => toàn bộ là T3
  37.         T3[nod] = T2[nod] = T1[nod] = len;
  38.         return;
  39.     }
  40.  
  41.     if (l == r){
  42.         // leaf
  43.         if (delta[nod] == 2)      T1[nod] = T2[nod] = len, T3[nod] = 0;
  44.         else if (delta[nod] == 1) T1[nod] = len, T2[nod] = T3[nod] = 0;
  45.         else                      T1[nod] = T2[nod] = T3[nod] = 0;
  46.         return;
  47.     }
  48.  
  49.     if (delta[nod] == 2){
  50.         // whole interval has +2; so >=1 and >=2 are full length
  51.         T1[nod] = T2[nod] = len;
  52.         // parts that become >=3 are where children had >=1
  53.         T3[nod] = T1[nod*2] + T1[nod*2+1];
  54.         return;
  55.     }
  56.     if (delta[nod] == 1){
  57.         // whole interval has +1 => >=1 is full length
  58.         T1[nod] = len;
  59.         // >=2 are positions where child had >=1
  60.         T2[nod] = T1[nod*2] + T1[nod*2+1];
  61.         // >=3 are positions where child had >=2
  62.         T3[nod] = T2[nod*2] + T2[nod*2+1];
  63.         return;
  64.     }
  65.     // delta == 0
  66.     T1[nod] = T1[nod*2] + T1[nod*2+1];
  67.     T2[nod] = T2[nod*2] + T2[nod*2+1];
  68.     T3[nod] = T3[nod*2] + T3[nod*2+1];
  69. }
  70.  
  71. //Nếu "khoảng" [l, r] bị bao hoàn toàn thì lấy toàn bộ
  72. //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
  73. //Nếu "khoảng" lá không bị bao thì phải bằng 0
  74. //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
  75.  
  76. void update(int nod, int l, int r, int u, int v, int val){
  77.     if (r < u || l > v) return;
  78.     if (l >= u && r <= v){
  79.         delta[nod] += val;
  80.         push_up(nod, l, r);
  81.         return;
  82.     }
  83.     int mid = (l+r) >> 1;
  84.     update(nod*2, l, mid, u, v, val);
  85.     update(nod*2+1, mid+1, r, u, v, val);
  86.     push_up(nod, l, r);
  87. }
  88.  
  89. signed main(){
  90.     ios_base::sync_with_stdio(false);
  91.     cin.tie(0);
  92.     #define Task "A"
  93.     if (fopen(Task".inp", "r")){
  94.         freopen(Task".inp", "r", stdin);
  95.         freopen(Task".out", "w", stdout);
  96.     }
  97.  
  98.     cin >> n;
  99.     up(i,1,n){
  100.         int x1, y1, x2, y2;
  101.         cin >> x1 >> y1 >> x2 >> y2;
  102.         tempY.push_back(y1);
  103.         tempY.push_back(y2);
  104.         events.push_back({x1, y1, y2, 1});
  105.         events.push_back({x2, y1, y2, -1});
  106.     }
  107.  
  108.     tempY.push_back(-MOD);
  109.     sort(tempY.begin(), tempY.end());
  110.     tempY.resize(unique(tempY.begin(), tempY.end()) - tempY.begin());
  111.     treesize = tempY.size()-1;
  112. //    tempY thêm phần tử -MOD để lấy lowerbound với chỉ số bắt đầu từ 1
  113. //    treesize = tempY.size()-1 vì phải bỏ qua phần tử -MOD;
  114.  
  115.  
  116.     sort(events.begin(), events.end(), comp);
  117.  
  118.     long long res = 0;
  119.     for (int i = 0; i < (int)(events.size()-1); i++){
  120.         int u = lower_bound(tempY.begin(), tempY.end(), events[i].y1) - tempY.begin();
  121.         int v = lower_bound(tempY.begin(), tempY.end(), events[i].y2) - tempY.begin();
  122.  
  123.  
  124.         update(1, 1, treesize-1, u, v-1, events[i].type);
  125.         res += 1ll * (T2[1] - T3[1]) * (events[i+1].x - events[i].x);
  126. //        Segment tree quản lý các "khoảng" giữa tọa độ điểm này và tọa độ điểm kia
  127. //        có treesize tọa độ điểm thì có treesize-1 "khoảng"
  128. //        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]
  129. //        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
  130.  
  131. //        cout << T1[1] << " " << T2[1] << " " << T3[1] << " " << res << " ";
  132. //        cout << u << " " << v << "\n";
  133.     }
  134.     cout << res;
  135. }
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147. /**Code Trâu**/
  148. //#include <bits/stdc++.h>
  149. //#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  150. //#define down(i,a,b) for (int i = (int)a; i >= (int)b; i--)
  151. //using namespace std;
  152. //
  153. //const int maxn = 5e2 + 10;
  154. //int n;
  155. //int a[maxn][maxn];
  156. //int MAXX = 500;
  157. //int MAXY = 500;
  158. //
  159. //signed main(){//code trau
  160. //    ios_base::sync_with_stdio(false);
  161. //    cin.tie(0);
  162. //    #define Task "A"
  163. //    if (fopen(Task".inp", "r")){
  164. //        freopen(Task".inp", "r", stdin);
  165. //        freopen(Task".out", "w", stdout);
  166. //    }
  167. //
  168. //    int maxx, maxy;
  169. //    maxx = -MAXX;
  170. //    maxy = -MAXX;
  171. //    cin >> n;
  172. //    up(i,1,n){
  173. //        int x1, y1, x2, y2;
  174. //        cin >> x1 >> y1 >> x2 >> y2;
  175. //        maxx = max(maxx, x2-1);
  176. //        maxy = max(maxy, y2-1);
  177. //        up(i, x1, x2-1){
  178. //            up(j, y1, y2-1){
  179. //                ++a[i][j];
  180. //            }
  181. //        }
  182. //    }
  183. //
  184. //    int cnt = 0;
  185. //    up(i,1,maxx){
  186. //        up(j,1,maxy){
  187. //            if (a[i][j] == 2) ++cnt;
  188. //        }
  189. //    }
  190. //    cout << cnt << "\n";
  191. //
  192. //
  193. //    down(j,maxy,1){
  194. //        up(i,1,maxx){
  195. //            cout << a[i][j] << " ";
  196. //        }
  197. //        cout << "\n";
  198. //    }
  199. //}
  200.  
Success #stdin #stdout 0.01s 9740KB
comments (?)
stdin
copy 
4
2 1 4 4
3 2 7 8
5 3 9 5
6 4 8 9
stdout
copy 
9
https://ideone.com/yve3f8
Area intersected by exactly 2 rectangles from n rectangles
language:
C++14 (gcc 8.3)
created:
74 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!