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. //events in sweep line
  14. //there are 2 type of events: opening and closing, represented by 1 and -1
  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. // Sort events by x; if equal, process "opening" events before "closing"
  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 for the maximum number of possible events (each rectangle adds one open and one close event)
  31. // maxn << 3 as an upper bound for the segment tree size over all events
  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.     //  whole interval has +3 -> full length for all tree at this node
  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 -> >=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. // If interval [l, r] is fully covered, take the full segment
  71. // If [l, r] is partially covered (and not a leaf), update based on children
  72. // If the leaf is not covered, its value must be 0
  73. // Warning: Without (l != r) case, segment tree might access child indices outside the declared range
  74.  
  75. void update(int nod, int l, int r, int u, int v, int val){
  76.     if (r < u || l > v) return;
  77.     if (l >= u && r <= v){
  78.         delta[nod] += val;
  79.         push_up(nod, l, r);
  80.         return;
  81.     }
  82.     int mid = (l+r) >> 1;
  83.     update(nod*2, l, mid, u, v, val);
  84.     update(nod*2+1, mid+1, r, u, v, val);
  85.     push_up(nod, l, r);
  86. }
  87.  
  88. signed main(){
  89.     ios_base::sync_with_stdio(false);
  90.     cin.tie(0);
  91.     #define Task "A"
  92.     if (fopen(Task".inp", "r")){
  93.         freopen(Task".inp", "r", stdin);
  94.         freopen(Task".out", "w", stdout);
  95.     }
  96.  
  97.     cin >> n;
  98.     up(i,1,n){
  99.         int x1, y1, x2, y2;
  100.         cin >> x1 >> y1 >> x2 >> y2;
  101.         tempY.push_back(y1);
  102.         tempY.push_back(y2);
  103.         events.push_back({x1, y1, y2, 1});
  104.         events.push_back({x2, y1, y2, -1});
  105.     }
  106.  
  107.     tempY.push_back(-MOD);
  108.     sort(tempY.begin(), tempY.end());
  109.     tempY.resize(unique(tempY.begin(), tempY.end()) - tempY.begin());
  110.     treesize = tempY.size()-1;
  111. 	// tempY includes an extra element -MOD so lower_bound starts from index 1
  112. 	// treesize = tempY.size() - 1 because we ignore the -MOD element
  113.  
  114.  
  115.     sort(events.begin(), events.end(), comp);
  116.  
  117.     long long res = 0;
  118.     for (int i = 0; i < (int)(events.size()-1); i++){
  119.         int u = lower_bound(tempY.begin(), tempY.end(), events[i].y1) - tempY.begin();
  120.         int v = lower_bound(tempY.begin(), tempY.end(), events[i].y2) - tempY.begin();
  121. 		// u and v are 1-based indexing
  122.  
  123.         update(1, 1, treesize-1, u, v-1, events[i].type);
  124.         res += 1ll * (T2[1] - T3[1]) * (events[i+1].x - events[i].x);
  125. 		// The segment tree manages "intervals" between consecutive coordinates
  126. 		// With treesize coordinate points, there are treesize-1 intervals
  127. 		// Each node with index v manages the interval [l, r]; when fully covered, its length is tempY[r+1] - tempY[l]
  128. 		// Thus, each query on coordinate range [u, v] corresponds to interval [u, v-1] in the segment tree
  129.     }
  130.     cout << res;
  131. }
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143. //#include <bits/stdc++.h>
  144. //#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  145. //#define down(i,a,b) for (int i = (int)a; i >= (int)b; i--)
  146. //using namespace std;
  147. //
  148. //const int maxn = 5e2 + 10;
  149. //int n;
  150. //int a[maxn][maxn];
  151. //int MAXX = 500;
  152. //int MAXY = 500;
  153. //
  154. //signed main(){
  155. //    ios_base::sync_with_stdio(false);
  156. //    cin.tie(0);
  157. //    #define Task "A"
  158. //    if (fopen(Task".inp", "r")){
  159. //        freopen(Task".inp", "r", stdin);
  160. //        freopen(Task".out", "w", stdout);
  161. //    }
  162. //
  163. //    int maxx, maxy;
  164. //    maxx = -MAXX;
  165. //    maxy = -MAXX;
  166. //    cin >> n;
  167. //    up(i,1,n){
  168. //        int x1, y1, x2, y2;
  169. //        cin >> x1 >> y1 >> x2 >> y2;
  170. //        maxx = max(maxx, x2-1);
  171. //        maxy = max(maxy, y2-1);
  172. //        up(i, x1, x2-1){
  173. //            up(j, y1, y2-1){
  174. //                ++a[i][j];
  175. //            }
  176. //        }
  177. //    }
  178. //
  179. //    int cnt = 0;
  180. //    up(i,1,maxx){
  181. //        up(j,1,maxy){
  182. //            if (a[i][j] == 2) ++cnt;
  183. //        }
  184. //    }
  185. //    cout << cnt << "\n";
  186. //
  187. //
  188. //    down(j,maxy,1){
  189. //        up(i,1,maxx){
  190. //            cout << a[i][j] << " ";
  191. //        }
  192. //        cout << "\n";
  193. //    }
  194. //}
  195.  
Success #stdin #stdout 0.01s 9728KB
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/JZg2EZ
Area intersected by exactly 2 rectangles from n rectangles (English comment)
language:
C++14 (gcc 8.3)
created:
115 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!