Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- clude<bits/stdc++.h>
- #include <cstring>
- #include <iostream>
- #define pie acos(-1)
- #define si(a) scanf("%d",&a)
- #define sii(a,b) scanf("%d %d",&a,&b)
- #define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
- #define sl(a) scanf("%lld",&a)
- #define sll(a,b) scanf("%lld %lld",&a,&b)
- #define slll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
- #define ss(st) scanf("%s",st)
- #define sch(ch) scanf("%ch",&ch)
- #define ps(a) printf("%s",a)
- #define newLine() printf("\n")
- #define pi(a) printf("%d",a)
- #define pii(a,b) printf("%d %d",a,b)
- #define piii(a,b,c) printf("%d %d %d",a,b,c)
- #define pl(a) printf("%lld",a)
- #define pll(a,b) printf("%lld %lld",a,b)
- #define plll(a,b,c) printf("%lld %lld %lld",a,b,c)
- #define pd(a) printf("%lf",a)
- #define pdd(a,b) printf("%lf %lf",a,b)
- #define pddd(a,b,c) printf("%lf %lf %lf",a,b,c)
- #define pch(c) printf("%ch",c)
- #define debug1(str,a) printf("%s=%d\n",str,a)
- #define debug2(str1,str2,a,b) printf("%s=%d %s=%d\n",str1,a,str2,b)
- #define debug3(str1,str2,str3,a,b,c) printf("%s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c)
- #define debug4(str1,str2,str3,str4,a,b,c,d) printf("%s=%d %s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c,str4,d)
- #define for0(i,n) for(i=0;i<n;i++)
- #define for1(i,n) for(i=1;i<=n;i++)
- #define forab(i,a,b) for(i=a;i<=b;i++)
- #define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
- #define nl puts("")
- #define sd(a) scanf("%lf",&a)
- #define sdd(a,b) scanf("%lf %lf",&a,&b)
- #define sddd(a,b,c) scanf("%lf %lf %lf",&a,&b,&c)
- #define sp printf(" ")
- #define ll long long int
- #define ull unsigned long long int
- #define MOD 1000000007
- #define mpr make_pair
- #define pub(x) push_back(x)
- #define pob(x) pop_back(x)
- #define mem(ara,value) memset(ara,value,sizeof(ara))
- #define INF INT_MAX
- #define eps 1e-9
- #define checkbit(n, pos) (n & (1<<pos))
- #define setbit(n, pos) (n (1<<pos))
- #define para(i,a,b,ara)\
- for(i=a;i<=b;i++){\
- if(i!=0){printf(" ");}\
- cout<<ara[i];\
- }\
- printf("\n");
- #define pvec(i,vec)\
- for(i=0;i<vec.size();i++){\
- if(i!=0){printf(" ");}\
- cout<<vec[i];\
- }\
- printf("\n");
- #define ppara(i,j,n,m,ara)\
- for(i=0;i<n;i++){\
- for(j=0;j<m;j++){\
- if(j!=0){printf(" ");}\
- cout<<ara[i][j];\
- }\
- printf("\n");\
- }
- #define ppstructara(i,j,n,m,ara)\
- for(i=0;i<n;i++){\
- printf("%d:\n",i);\
- for(j=0;j<m;j++){\
- cout<<ara[i][j];printf("\n");\
- }\
- }
- #define ppvec(i,j,n,vec)\
- for(i=0;i<n;i++){\
- printf("%d:",i);\
- for(j=0;j<vec[i].size();j++){\
- if(j!=0){printf(" ");}\
- cout<<vec[i][j];\
- }\
- printf("\n");\
- }
- #define ppstructvec(i,j,n,vec)\
- for(i=0;i<n;i++){\
- printf("%d:",i);\
- for(j=0;j<vec[i].size();j++){\
- cout<<vec[i][j];printf("\n");\
- }\
- }
- #define sara(i,a,b,ara)\
- for(i=a;i<=b;i++){\
- scanf("%d",&ara[i]);\
- }
- #define pstructara(i,a,b,ara)\
- for(i=a;i<=b;i++){\
- cout<<ara[i];nl;\
- }
- #define pstructvec(i,vec)\
- for(i=0;i<vec.size();i++){\
- cout<<vec[i];nl;\
- }
- #define pstructstl(stl,x)\
- for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
- x=*it;\
- cout<<x;nl;\
- }\
- nl;
- #define pstl(stl)\
- for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
- if(it!=stl.begin()){sp;}\
- pi(*it);\
- }\
- nl;
- #define ppairvec(i,vec)\
- for(i=0;i<vec.size();i++){\
- cout<<vec[i].first;sp;cout<<vec[i].second;printf("\n");\
- }
- #define ppairara(i,a,b,ara)\
- for(i=a;i<=b;i++){\
- cout<<ara[i].first;sp;cout<<ara[i].second;printf("\n");\
- }
- #define pppairvec(i,j,n,vec)\
- for(i=0;i<n;i++){\
- printf("%d:\n",i);\
- for(j=0;j<vec[i].size();j++){\
- cout<<vec[i][j].first;sp;cout<<vec[i][j].second;nl;\
- }\
- }
- #define pppairara(i,j,n,m,ara)\
- for(i=0;i<n;i++){\
- printf("%d:\n",i);\
- for(j=0;j<m;j++){\
- cout<<ara[i][j].first;printf(" ");cout<<ara[i][j].second;nl;\
- }\
- }
- #define SZ 30010
- using namespace std;
- //bool status[100010];
- //vector <int> prime;
- //void siv(){
- // int N = 100005, i, j; prime.clear();
- // int sq = sqrt(N);
- // for(i = 4; i <= N; i += 2){ status[i] = true; }
- // for(i = 3; i <= sq; i+= 2){
- // if(status[i] == false){
- // for(j = i * i; j <= N; j += i){ status[j] = true; }
- // }
- // }
- // status[1] = true;
- // for1(i, N){ if(!status[i]){ prime.pub(i); } }
- //}
- int add(int _a, int _b){
- _a = (_a + MOD) % MOD;
- _b = (_b + MOD) % MOD;
- return (_a + _b) % MOD;
- }
- int mul(int _a, int _b){
- _a = (_a + MOD) % MOD;
- _b = (_b + MOD) % MOD;
- return ((ll)((ll)_a * (ll)_b)) % MOD;
- }
- struct REC{
- ll x1, y1, x2, y2;
- REC(){}
- REC(ll _x1, ll _y1, ll _x2, ll _y2){
- x1 = _x1, y1 = _y1, x2 = _x2, y2 = _y2;
- }
- }rec[SZ];
- struct SEG{
- ll x, y1, y2, polarity;
- SEG(){}
- SEG(ll _x, ll _y1, ll _y2, ll _polarity){
- x = _x, y1 = _y1, y2 = _y2, polarity = _polarity;
- }
- }seg[2 * SZ];
- struct TREE{
- ll mn, min_sum, lz;
- TREE(){}
- TREE(ll _mn, ll _min_sum, ll _lz){
- mn = _mn, min_sum = _min_sum, lz = _lz;
- }
- }tree[4 * 2 * SZ + 10];
- ll n;
- vector <ll> check_poll;
- bool cmp(SEG lhs, SEG rhs){
- if(lhs.x == rhs.x){
- return lhs.polarity > rhs.polarity;
- } return lhs.x < rhs.x;
- }
- void input(){
- ll i, j = 0;
- check_poll.clear();
- sl(n);
- for0(i, n){
- sll(rec[i].x1, rec[i].y1), sll(rec[i].x2, rec[i].y2);
- check_poll.push_back(rec[i].y1), check_poll.push_back(rec[i].y2);
- seg[j++] = SEG(rec[i].x1, rec[i].y1, rec[i].y2, +1);
- seg[j++] = SEG(rec[i].x2, rec[i].y1, rec[i].y2, -1);
- }
- sort(seg, seg + 2 * n, cmp);
- sort(check_poll.begin(), check_poll.end());
- check_poll.erase(unique(check_poll.begin(), check_poll.end()), check_poll.end());
- }
- void mrg(ll iter){
- tree[iter].mn = min(tree[2 * iter + 1].mn, tree[2 * iter + 2].mn);
- if(tree[2 * iter + 1].mn == tree[2 * iter + 2].mn){
- tree[iter].min_sum = tree[2 * iter + 1].min_sum + tree[2 * iter + 2].min_sum;
- }
- else if(tree[2 * iter + 1].mn < tree[2 * iter + 2].mn){
- tree[iter].min_sum = tree[2 * iter + 1].min_sum;
- }
- else{
- tree[iter].min_sum = tree[2 * iter + 2].min_sum;
- }
- }
- void make_tree(ll lo, ll hi, ll iter){
- ll mid = (lo + hi) >> 1ll;
- tree[iter].lz = 0;
- if(lo == hi){
- tree[iter].mn = 0;
- tree[iter].min_sum = check_poll[lo + 1] - check_poll[lo];
- return;
- }
- else{
- make_tree(lo, mid, 2 * iter + 1);
- make_tree(mid + 1, hi, 2 * iter + 2);
- mrg(iter);
- }
- }
- void lazy_up(ll iter, ll v){
- tree[iter].mn += v;
- tree[iter].lz += v;
- }
- void push_down(ll iter){
- lazy_up(2 * iter + 1, tree[iter].lz);
- lazy_up(2 * iter + 2, tree[iter].lz);
- tree[iter].lz = 0;
- }
- void update(ll lo, ll hi, ll iter, ll l, ll r, ll v){
- ll mid = (lo + hi) >> 1ll;
- if(l <= lo && r >= hi){
- lazy_up(iter, v);
- return;
- }
- else if(l > hi || r < lo){ return; }
- else{
- push_down(iter);
- update(lo, mid, 2 * iter + 1, l, r, v);
- update(mid + 1, hi, 2 * iter + 2, l, r, v);
- mrg(iter);
- }
- }
- void solve(){
- ll i, j, sz = check_poll.size(), x, y;
- ll ret = 0;
- make_tree(0, sz - 2, 0);
- ll l = lower_bound(check_poll.begin(), check_poll.end(), seg[0].y1) - check_poll.begin();
- ll r = lower_bound(check_poll.begin(), check_poll.end(), seg[0].y2) - check_poll.begin(); r--;
- update(0, sz - 2, 0, l, r, seg[0].polarity);
- for(i = 1; i < 2 * n; i++){
- l = lower_bound(check_poll.begin(), check_poll.end(), seg[i].y1) - check_poll.begin();
- r = lower_bound(check_poll.begin(), check_poll.end(), seg[i].y2) - check_poll.begin(); r--;
- x = seg[i].x - seg[i - 1].x;
- y = check_poll.back() - check_poll[0];
- if(tree[0].mn <= 0){
- y -= tree[0].min_sum;
- }
- ret += (x * y);
- update(0, sz - 2, 0, l, r, seg[i].polarity);
- }
- // pl(tree[0].mn); nl;
- pl(ret); nl;
- }
- int main(){
- // freopen("input.txt","r",stdin);
- // freopen("output.txt", "w", stdout);
- int cs, ts;
- si(ts);
- for0(cs, ts){
- input();
- printf("Case %d: ", cs + 1);
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement