Advertisement
Guest User

fare_gatis

a guest
Jan 12th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<ll, ll> pii;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11.  
  12. vector<int> xc, yc, sx, sy;
  13.  
  14. const int N = (int)1e5 + 9;
  15.  
  16. int cnt1[N], cnt2[N], cnt3[N], cnt4[N];
  17. set<int> c1, c2, c3, c4;
  18.  
  19. int main(){
  20.     int n;
  21.     scanf("%d", &n);
  22.     char ty[n];
  23.     int x1[n];
  24.     int y1[n];
  25.     int x2[n];
  26.     int y2[n];
  27.     for(int i = 0 ;i < n; i ++ ){
  28.         cin >> ty[i];
  29.         scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
  30.         xc.push_back(x1[i]);
  31.         yc.push_back(y1[i]);
  32.         sx.push_back(x2[i]);
  33.         sy.push_back(y2[i]);
  34.     }
  35.     sort(xc.begin(), xc.end());
  36.     sort(yc.begin(), yc.end());
  37.     sort(sx.begin(), sx.end());
  38.     sort(sy.begin(), sy.end());
  39.     xc.resize(unique(xc.begin(), xc.end()) - xc.begin());
  40.     yc.resize(unique(yc.begin(), yc.end()) - yc.begin());
  41.     sx.resize(unique(sx.begin(), sx.end()) - sx.begin());
  42.     sy.resize(unique(sy.begin(), sy.end()) - sy.begin());
  43.     int s1, s2;
  44.     ll answ;
  45.     for(int i = 0 ; i < n; i ++ ){
  46.         x1[i] = lower_bound(xc.begin(), xc.end(), x1[i]) - xc.begin();
  47.         y1[i] = lower_bound(yc.begin(), yc.end(), y1[i]) - yc.begin();
  48.         x2[i] = lower_bound(sx.begin(), sx.end(), x2[i]) - sx.begin();
  49.         y2[i] = lower_bound(sy.begin(), sy.end(), y2[i]) - sy.begin();
  50.         if(ty[i] == '+'){
  51.             cnt1[x1[i]] ++ ;
  52.             if(cnt1[x1[i]] == 1)
  53.                 c1.insert(x1[i]);
  54.             cnt2[y1[i]] ++ ;
  55.             if(cnt2[y1[i]] == 1)
  56.                 c2.insert(y1[i]);
  57.             cnt3[x2[i]] ++ ;
  58.             if(cnt3[x2[i]] == 1)
  59.                 c3.insert(x2[i]);
  60.             cnt4[y2[i]] ++ ;
  61.             if(cnt4[y2[i]] == 1)
  62.                 c4.insert(y2[i]);
  63.            
  64.         }
  65.         else{
  66.             cnt1[x1[i]] -- ;
  67.             if(cnt1[x1[i]] == 0)
  68.                 c1.erase(x1[i]);
  69.             cnt2[y1[i]] -- ;
  70.             if(cnt2[y1[i]] == 0)
  71.                 c2.erase(y1[i]);
  72.             cnt3[x2[i]] -- ;
  73.             if(cnt3[x2[i]] == 0)
  74.                 c3.erase(x2[i]);
  75.             cnt4[y2[i]] -- ;
  76.             if(cnt4[y2[i]] == 0)
  77.                 c4.erase(y2[i]);
  78.         }
  79.         if(c1.empty() || c2.empty() || c3.empty() || c4.empty()){
  80.             printf("0\n");
  81.             continue;
  82.         }
  83.         auto it = c3.begin();
  84.         s1 = sx[*it];
  85.         it = c1.end();
  86.         -- it;
  87.         s1 -= xc[*it];
  88.         // !!!!!!!!!!!!!!!1
  89.         it = c4.begin();
  90.         s2 = sy[*it];
  91.         it = c2.end();
  92.         -- it;
  93.         s2 -= yc[*it];
  94.         answ = 1ll * s1 * s2;
  95.         answ = max(answ, 0ll);
  96.         printf("%lli\n", answ);
  97.     }
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement