Advertisement
Guest User

Untitled

a guest
Feb 19th, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.13 KB | None | 0 0
  1. clude<bits/stdc++.h>
  2. #include <cstring>
  3. #include <iostream>
  4. #define pie acos(-1)
  5. #define si(a) scanf("%d",&a)
  6. #define sii(a,b) scanf("%d %d",&a,&b)
  7. #define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
  8. #define sl(a) scanf("%lld",&a)
  9. #define sll(a,b) scanf("%lld %lld",&a,&b)
  10. #define slll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
  11. #define ss(st) scanf("%s",st)
  12. #define sch(ch) scanf("%ch",&ch)
  13. #define ps(a) printf("%s",a)
  14. #define newLine() printf("\n")
  15. #define pi(a) printf("%d",a)
  16. #define pii(a,b) printf("%d %d",a,b)
  17. #define piii(a,b,c) printf("%d %d %d",a,b,c)
  18. #define pl(a) printf("%lld",a)
  19. #define pll(a,b) printf("%lld %lld",a,b)
  20. #define plll(a,b,c) printf("%lld %lld %lld",a,b,c)
  21. #define pd(a) printf("%lf",a)
  22. #define pdd(a,b) printf("%lf %lf",a,b)
  23. #define pddd(a,b,c) printf("%lf %lf %lf",a,b,c)
  24. #define pch(c) printf("%ch",c)
  25. #define debug1(str,a) printf("%s=%d\n",str,a)
  26. #define debug2(str1,str2,a,b) printf("%s=%d %s=%d\n",str1,a,str2,b)
  27. #define debug3(str1,str2,str3,a,b,c) printf("%s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c)
  28. #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)
  29. #define for0(i,n) for(i=0;i<n;i++)
  30. #define for1(i,n) for(i=1;i<=n;i++)
  31. #define forab(i,a,b) for(i=a;i<=b;i++)
  32. #define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
  33. #define nl puts("")
  34. #define sd(a) scanf("%lf",&a)
  35. #define sdd(a,b) scanf("%lf %lf",&a,&b)
  36. #define sddd(a,b,c) scanf("%lf %lf %lf",&a,&b,&c)
  37. #define sp printf(" ")
  38. #define ll long long int
  39. #define ull unsigned long long int
  40. #define MOD 1000000007
  41. #define mpr make_pair
  42. #define pub(x) push_back(x)
  43. #define pob(x) pop_back(x)
  44. #define mem(ara,value) memset(ara,value,sizeof(ara))
  45. #define INF INT_MAX
  46. #define eps 1e-9
  47. #define checkbit(n, pos) (n & (1<<pos))
  48. #define setbit(n, pos) (n (1<<pos))
  49. #define para(i,a,b,ara)\
  50. for(i=a;i<=b;i++){\
  51. if(i!=0){printf(" ");}\
  52. cout<<ara[i];\
  53. }\
  54. printf("\n");
  55. #define pvec(i,vec)\
  56. for(i=0;i<vec.size();i++){\
  57. if(i!=0){printf(" ");}\
  58. cout<<vec[i];\
  59. }\
  60. printf("\n");
  61. #define ppara(i,j,n,m,ara)\
  62. for(i=0;i<n;i++){\
  63. for(j=0;j<m;j++){\
  64. if(j!=0){printf(" ");}\
  65. cout<<ara[i][j];\
  66. }\
  67. printf("\n");\
  68. }
  69. #define ppstructara(i,j,n,m,ara)\
  70. for(i=0;i<n;i++){\
  71. printf("%d:\n",i);\
  72. for(j=0;j<m;j++){\
  73. cout<<ara[i][j];printf("\n");\
  74. }\
  75. }
  76. #define ppvec(i,j,n,vec)\
  77. for(i=0;i<n;i++){\
  78. printf("%d:",i);\
  79. for(j=0;j<vec[i].size();j++){\
  80. if(j!=0){printf(" ");}\
  81. cout<<vec[i][j];\
  82. }\
  83. printf("\n");\
  84. }
  85. #define ppstructvec(i,j,n,vec)\
  86. for(i=0;i<n;i++){\
  87. printf("%d:",i);\
  88. for(j=0;j<vec[i].size();j++){\
  89. cout<<vec[i][j];printf("\n");\
  90. }\
  91. }
  92. #define sara(i,a,b,ara)\
  93. for(i=a;i<=b;i++){\
  94. scanf("%d",&ara[i]);\
  95. }
  96. #define pstructara(i,a,b,ara)\
  97. for(i=a;i<=b;i++){\
  98. cout<<ara[i];nl;\
  99. }
  100. #define pstructvec(i,vec)\
  101. for(i=0;i<vec.size();i++){\
  102. cout<<vec[i];nl;\
  103. }
  104. #define pstructstl(stl,x)\
  105. for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
  106. x=*it;\
  107. cout<<x;nl;\
  108. }\
  109. nl;
  110. #define pstl(stl)\
  111. for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
  112. if(it!=stl.begin()){sp;}\
  113. pi(*it);\
  114. }\
  115. nl;
  116. #define ppairvec(i,vec)\
  117. for(i=0;i<vec.size();i++){\
  118. cout<<vec[i].first;sp;cout<<vec[i].second;printf("\n");\
  119. }
  120. #define ppairara(i,a,b,ara)\
  121. for(i=a;i<=b;i++){\
  122. cout<<ara[i].first;sp;cout<<ara[i].second;printf("\n");\
  123. }
  124. #define pppairvec(i,j,n,vec)\
  125. for(i=0;i<n;i++){\
  126. printf("%d:\n",i);\
  127. for(j=0;j<vec[i].size();j++){\
  128. cout<<vec[i][j].first;sp;cout<<vec[i][j].second;nl;\
  129. }\
  130. }
  131. #define pppairara(i,j,n,m,ara)\
  132. for(i=0;i<n;i++){\
  133. printf("%d:\n",i);\
  134. for(j=0;j<m;j++){\
  135. cout<<ara[i][j].first;printf(" ");cout<<ara[i][j].second;nl;\
  136. }\
  137. }
  138. #define SZ 30010
  139. using namespace std;
  140. //bool status[100010];
  141. //vector <int> prime;
  142. //void siv(){
  143. // int N = 100005, i, j; prime.clear();
  144. // int sq = sqrt(N);
  145. // for(i = 4; i <= N; i += 2){ status[i] = true; }
  146. // for(i = 3; i <= sq; i+= 2){
  147. // if(status[i] == false){
  148. // for(j = i * i; j <= N; j += i){ status[j] = true; }
  149. // }
  150. // }
  151. // status[1] = true;
  152. // for1(i, N){ if(!status[i]){ prime.pub(i); } }
  153. //}
  154. int add(int _a, int _b){
  155. _a = (_a + MOD) % MOD;
  156. _b = (_b + MOD) % MOD;
  157. return (_a + _b) % MOD;
  158. }
  159. int mul(int _a, int _b){
  160. _a = (_a + MOD) % MOD;
  161. _b = (_b + MOD) % MOD;
  162. return ((ll)((ll)_a * (ll)_b)) % MOD;
  163. }
  164. struct REC{
  165. ll x1, y1, x2, y2;
  166. REC(){}
  167. REC(ll _x1, ll _y1, ll _x2, ll _y2){
  168. x1 = _x1, y1 = _y1, x2 = _x2, y2 = _y2;
  169. }
  170. }rec[SZ];
  171. struct SEG{
  172. ll x, y1, y2, polarity;
  173. SEG(){}
  174. SEG(ll _x, ll _y1, ll _y2, ll _polarity){
  175. x = _x, y1 = _y1, y2 = _y2, polarity = _polarity;
  176. }
  177. }seg[2 * SZ];
  178. struct TREE{
  179. ll mn, min_sum, lz;
  180. TREE(){}
  181. TREE(ll _mn, ll _min_sum, ll _lz){
  182. mn = _mn, min_sum = _min_sum, lz = _lz;
  183. }
  184. }tree[4 * 2 * SZ + 10];
  185. ll n;
  186. vector <ll> check_poll;
  187. bool cmp(SEG lhs, SEG rhs){
  188. if(lhs.x == rhs.x){
  189. return lhs.polarity > rhs.polarity;
  190. } return lhs.x < rhs.x;
  191. }
  192. void input(){
  193. ll i, j = 0;
  194. check_poll.clear();
  195. sl(n);
  196. for0(i, n){
  197. sll(rec[i].x1, rec[i].y1), sll(rec[i].x2, rec[i].y2);
  198. check_poll.push_back(rec[i].y1), check_poll.push_back(rec[i].y2);
  199. seg[j++] = SEG(rec[i].x1, rec[i].y1, rec[i].y2, +1);
  200. seg[j++] = SEG(rec[i].x2, rec[i].y1, rec[i].y2, -1);
  201. }
  202. sort(seg, seg + 2 * n, cmp);
  203. sort(check_poll.begin(), check_poll.end());
  204. check_poll.erase(unique(check_poll.begin(), check_poll.end()), check_poll.end());
  205. }
  206. void mrg(ll iter){
  207. tree[iter].mn = min(tree[2 * iter + 1].mn, tree[2 * iter + 2].mn);
  208. if(tree[2 * iter + 1].mn == tree[2 * iter + 2].mn){
  209. tree[iter].min_sum = tree[2 * iter + 1].min_sum + tree[2 * iter + 2].min_sum;
  210. }
  211. else if(tree[2 * iter + 1].mn < tree[2 * iter + 2].mn){
  212. tree[iter].min_sum = tree[2 * iter + 1].min_sum;
  213. }
  214. else{
  215. tree[iter].min_sum = tree[2 * iter + 2].min_sum;
  216. }
  217. }
  218. void make_tree(ll lo, ll hi, ll iter){
  219. ll mid = (lo + hi) >> 1ll;
  220. tree[iter].lz = 0;
  221. if(lo == hi){
  222. tree[iter].mn = 0;
  223. tree[iter].min_sum = check_poll[lo + 1] - check_poll[lo];
  224. return;
  225. }
  226. else{
  227. make_tree(lo, mid, 2 * iter + 1);
  228. make_tree(mid + 1, hi, 2 * iter + 2);
  229. mrg(iter);
  230. }
  231. }
  232. void lazy_up(ll iter, ll v){
  233. tree[iter].mn += v;
  234. tree[iter].lz += v;
  235. }
  236. void push_down(ll iter){
  237. lazy_up(2 * iter + 1, tree[iter].lz);
  238. lazy_up(2 * iter + 2, tree[iter].lz);
  239. tree[iter].lz = 0;
  240. }
  241. void update(ll lo, ll hi, ll iter, ll l, ll r, ll v){
  242. ll mid = (lo + hi) >> 1ll;
  243. if(l <= lo && r >= hi){
  244. lazy_up(iter, v);
  245. return;
  246. }
  247. else if(l > hi || r < lo){ return; }
  248. else{
  249. push_down(iter);
  250. update(lo, mid, 2 * iter + 1, l, r, v);
  251. update(mid + 1, hi, 2 * iter + 2, l, r, v);
  252. mrg(iter);
  253. }
  254. }
  255. void solve(){
  256. ll i, j, sz = check_poll.size(), x, y;
  257. ll ret = 0;
  258. make_tree(0, sz - 2, 0);
  259. ll l = lower_bound(check_poll.begin(), check_poll.end(), seg[0].y1) - check_poll.begin();
  260. ll r = lower_bound(check_poll.begin(), check_poll.end(), seg[0].y2) - check_poll.begin(); r--;
  261. update(0, sz - 2, 0, l, r, seg[0].polarity);
  262. for(i = 1; i < 2 * n; i++){
  263. l = lower_bound(check_poll.begin(), check_poll.end(), seg[i].y1) - check_poll.begin();
  264. r = lower_bound(check_poll.begin(), check_poll.end(), seg[i].y2) - check_poll.begin(); r--;
  265. x = seg[i].x - seg[i - 1].x;
  266. y = check_poll.back() - check_poll[0];
  267. if(tree[0].mn <= 0){
  268. y -= tree[0].min_sum;
  269. }
  270. ret += (x * y);
  271. update(0, sz - 2, 0, l, r, seg[i].polarity);
  272. }
  273. // pl(tree[0].mn); nl;
  274. pl(ret); nl;
  275. }
  276. int main(){
  277. // freopen("input.txt","r",stdin);
  278. // freopen("output.txt", "w", stdout);
  279. int cs, ts;
  280. si(ts);
  281. for0(cs, ts){
  282. input();
  283. printf("Case %d: ", cs + 1);
  284. solve();
  285. }
  286. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement