YEZAELP

SMMR-169: Thailand 4.0

Mar 23rd, 2021 (edited)
141
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using lli = long long;
  6. using pL = pair <lli, lli>;
  7. using pLL = pair <pL, pL>;
  8.  
  9. int main(){
  10.  
  11.     int n;
  12.     scanf("%d", &n);
  13.  
  14.     vector <pLL> event;
  15.  
  16.     for(int i=1;i<=n;i++){
  17.         lli x1, x2, y1, y2;
  18.         scanf("%lld%lld%lld%lld", &x1, &x2, &y1, &y2);
  19.         event.push_back({{x1, 2}, {y1, y2}});
  20.         event.push_back({{x2, 1}, {y1, y2}});
  21.     }
  22.  
  23.     sort(event.begin(), event.end());
  24.  
  25.     multiset <pL> H;
  26.     lli pre_x = -1, ans = 0;
  27.     for(auto e: event){
  28.  
  29.         lli x, ev, y1, y2;
  30.         x = e.first.first;
  31.         ev = e.first.second;
  32.         y1 = e.second.first;
  33.         y2 = e.second.second;
  34.  
  35.         if(pre_x == -1){
  36.             pre_x = x;
  37.             H.insert({y2, 1}); // 1 delete
  38.             H.insert({y1, 2}); // 2 insert
  39.             continue;
  40.         }
  41.  
  42.         // calculate area
  43.             // find x
  44.             lli sum_x = x - pre_x;
  45.             // find y
  46.             lli sum_y = 0, pre_y = -1, cnt = 0;
  47.             for(auto h: H){
  48.                 if(h.second == 2) {
  49.                     if(pre_y == -1) pre_y = h.first;
  50.                     cnt ++;
  51.                 }
  52.                 else{
  53.                     cnt --;
  54.                     if(cnt == 0){
  55.                         sum_y += h.first - pre_y;
  56.                         pre_y = -1;
  57.                     }
  58.                 }
  59.             }
  60.             // area = x * y
  61.             ans += (lli) sum_x * sum_y;
  62.  
  63.         // if ev = 1, delete H // ev = 2, insert H
  64.         if(ev == 1){
  65.             H.erase(H.find({y2, 1})); // 1 delete
  66.             H.erase(H.find({y1, 2})); // 2 insert
  67.         }
  68.         else if(ev == 2){
  69.             H.insert({y2, 1}); // 1 delete
  70.             H.insert({y1, 2}); // 2 insert
  71.         }
  72.  
  73.         // set variable
  74.         pre_x = x;
  75.     }
  76.  
  77.     printf("%lld", ans);
  78.  
  79.     return 0;
  80. }
  81.  
RAW Paste Data Copied