Advertisement
Guest User

Untitled

a guest
Oct 18th, 2017
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.31 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<string.h>
  4. #include<algorithm>
  5. #include<vector>
  6. #define ff first
  7. #define ss second
  8. #define m_p make_pair
  9. #define pb push_back
  10. #define ll long long
  11. using namespace std;
  12. struct data
  13. {
  14.     int x,y1,y2,v;
  15. };
  16. bool cmp (data a,data other)
  17. {
  18.     return a.x < other.x ;
  19. }
  20. vector<data>evnt;
  21. data pack(int _x,int _y1,int _y2,int _v)
  22. {
  23.     data tmp;
  24.     tmp.x=_x;
  25.     tmp.y1=_y1;
  26.     tmp.y2=_y2;
  27.     tmp.v=_v;
  28.     return tmp;
  29. }
  30. const int maxN = 3100000;
  31. pair<int,int> tree[maxN];
  32. int lft[maxN],rgt[maxN],lazy[maxN],last;
  33. void crt(int cn)
  34. {
  35.     if(lft[cn]==0)
  36.     {
  37.          tree[last]=m_p(0,0);
  38.          lft[cn]=last,lazy[last]=0,last++;
  39.          lft[lft[cn]]=rgt[lft[cn]]=0;
  40.     }
  41.     if(rgt[cn]==0)
  42.     {
  43.         tree[last]=m_p(0,0);
  44.         rgt[cn]=last,lazy[last]=0,last++;
  45.         lft[rgt[cn]]=rgt[rgt[cn]]=0;
  46.     }
  47. }
  48. int mx=0;
  49. void merge(int cn,int ln,int rn,ll carry)
  50. {
  51.     if(lazy[cn]+carry==mx) tree[cn].ff=tree[ln].ff + tree[rn].ff;
  52.     tree[cn].ss = max(tree[cn].ss,max(tree[ln].ss,tree[rn].ss));
  53. }
  54. void update(int cn,int st,int ed,int l,int r,int v,ll carry=0)
  55. {
  56.     if(ed<l || st>r) return;
  57.     mx=max(mx,tree[cn].ss);
  58.     if(st>=l && ed<=r)
  59.     {
  60.         lazy[cn]+=v;
  61.         tree[cn].ss+=carry+lazy[cn];
  62.         if(lazy[cn]+carry==mx) tree[cn].ff=ed-st+1;
  63.         else
  64.         {
  65.             if(st==ed) tree[cn].ff=0,tree[cn].ss=0;
  66.             else
  67.             {
  68.                 crt(cn);
  69.                 merge(cn,lft[cn],rgt[cn],carry);
  70.             }
  71.         }
  72.         return;
  73.     }
  74.     int mid=(st+ed)>>1;
  75.     crt(cn);
  76.     update(lft[cn],st,mid,l,r,v,carry+lazy[cn]);
  77.     update(rgt[cn],mid+1,ed,l,r,v,carry+lazy[cn]);
  78.     merge(cn,lft[cn],rgt[cn],carry);
  79.     mx=max(mx,tree[cn].ss);
  80.     //cout<<st<<" "<<ed<<" -> "<<tree[cn].ss<<endl;
  81. }
  82. int main()
  83. {
  84.     int kase,m,n;
  85.     scanf("%d",&kase);
  86.     for(int ks=1; ks<=kase; ks++)
  87.     {
  88.         scanf("%d",&n);
  89.         int mny=1000000000,mxy=0,power;
  90.         for(int i=1; i<=n; i++)
  91.         {
  92.           int x1,y1,x2,y2;
  93.             scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
  94.             scanf("%d",&power);
  95.             evnt.pb(pack(x1,y1,y2-1,1*power)),evnt.pb(pack(x2,y1,y2-1,-1*power));
  96.             mny=min(mny,min(y1,y2)),mxy=max(mxy,max(y1,y2));
  97.         }
  98.         sort(evnt.begin(),evnt.end(),cmp);
  99.         int ind = 0, pre = evnt[0].x;
  100.  
  101. //        tree[1]=m_p(0,0);
  102. //        lazy[1]=lft[1]=rgt[1]=0;
  103. memset(tree,0,sizeof(tree));
  104. memset(lft,0,sizeof(lft));
  105. memset(rgt,0,sizeof(rgt));
  106.         last=2;
  107.  
  108.  
  109.         while(ind < evnt.size() && evnt[ind].x == evnt[0].x )
  110.         {
  111.              //cout<<evnt[ind].y1<<" <begin> "<<evnt[ind].y2<<" "<<evnt[ind].v<<endl;
  112.             update(1,mny,mxy,evnt[ind].y1,evnt[ind].y2,evnt[ind].v),ind++;
  113.         }
  114.         ll ans=0;
  115.         while(ind < evnt.size() )
  116.         {
  117.             int cur=evnt[ind].x;
  118.             ll delx = cur - pre,dely = tree[1].ff;
  119.             pre=cur;
  120.             ans += delx * dely ;
  121.             while(ind < evnt.size() && evnt[ind].x == cur)
  122.                 {
  123.                     //cout<<evnt[ind].y1<<" <middle> "<<evnt[ind].y2<<" "<<evnt[ind].v<<endl;
  124.                     update(1,mny,mxy,evnt[ind].y1,evnt[ind].y2,evnt[ind].v),ind++;
  125.                 }
  126.         }
  127.  
  128.     cout<<mx<<" "<<ans<<endl;
  129.  
  130.  
  131.  
  132.             tree[1]=m_p(0,0);
  133.         lazy[1]=lft[1]=rgt[1]=0;
  134.         last=2;ind=0;
  135.         ans=0;
  136.  
  137.         while(ind < evnt.size() && evnt[ind].x == evnt[0].x )
  138.         {
  139.              //cout<<evnt[ind].y1<<" <begin> "<<evnt[ind].y2<<" "<<evnt[ind].v<<endl;
  140.             update(1,mny,mxy,evnt[ind].y1,evnt[ind].y2,evnt[ind].v),ind++;
  141.         }
  142.         cout<<tree[1].ff<<endl;
  143.         ans=0;
  144.         while(ind < evnt.size() )
  145.         {
  146.             int cur=evnt[ind].x;
  147.             ll delx = cur - pre,dely = tree[1].ff;
  148.             pre=cur;
  149.             ans += delx * dely ;
  150.             while(ind < evnt.size() && evnt[ind].x == cur)
  151.                 {
  152.                     //cout<<evnt[ind].y1<<" <middle> "<<evnt[ind].y2<<" "<<evnt[ind].v<<endl;
  153.                     update(1,mny,mxy,evnt[ind].y1,evnt[ind].y2,evnt[ind].v),ind++;
  154.                 }
  155.         }
  156.  
  157.  
  158.          evnt.clear();
  159.         printf("Case %d: %lld\n",ks,ans);
  160.  
  161.     }
  162. }
  163. /*
  164. 2
  165. 3
  166. 0 3 4 6 1
  167. 1 4 6 8 2
  168. 2 0 8 5 3
  169. 1
  170. 0 0 1000 1000 7
  171. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement