Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: xildar91
- PROG: humble
- LANG: C++11
- */
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef vector<int> vi;
- typedef vector<ll> vll;
- int inf_int=2e9;
- ll inf_ll=2e18;
- typedef pair<int,int> pii;
- #define pb push_back
- const double pi=3.1415926535898;
- #define dout if(debug) cout
- #define fi first
- #define se second
- #define sp setprecision
- #define sz size()
- #define x1 gfgs
- #define y1 asd
- #define rank asdsad
- bool debug=0;
- const int maxn=1e5+7;
- void solve()
- {
- int n;
- cin >> n;
- ll x1[n],y1[n],x2[n],y2[n];;
- vector<pair<pair<ll,ll> ,ll> >a;
- for(int i=0;i<n;i++)
- {
- cin >> x1[i]>>y2[i]>>x2[i]>>y1[i];
- a.pb({{x1[i],0},i});
- a.pb({{x2[i],1},i});
- }
- sort(a.begin(),a.end());
- ll ans=0;
- set<pair<pii,int> > s;
- ll prev;
- for(int i=0;i<a.sz;i++)
- {
- if(!i)
- {
- int in=a[i].se;
- s.insert({{y1[in],y2[in]},in});
- prev=a[i].fi.fi;
- }
- else
- {
- ll dis=a[i].fi.fi-prev;
- ll mn=-inf_ll;
- for(auto x:s)
- {
- mn=max(mn,(ll)x.fi.fi);
- ll val=max((ll)0,(x.fi.se-mn)*dis);
- ans+=val;
- mn=max(mn,(ll)x.fi.se);
- }
- if(a[i].fi.se==1)
- {
- int in=a[i].se;
- s.erase({{y1[in],y2[in]},in});
- }
- else
- {
- int in=a[i].se;
- s.insert({{y1[in],y2[in]},in});
- }
- prev=a[i].fi.fi;
- }
- }
- cout << ans;
- }
- #define FILE "B-large"
- int main()
- {
- // freopen("input.txt","r",stdin);
- // freopen("output.txt","w",stdout);
- // freopen(FILE".in","r",stdin);
- // freopen(FILE".out","w",stdout);
- if(!debug)
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- }
- int t=1;
- while(t--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment