Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<iostream>
- #include<string.h>
- #include<algorithm>
- #include<vector>
- #define ff first
- #define ss second
- #define m_p make_pair
- #define pb push_back
- #define ll long long
- using namespace std;
- struct data
- {
- int x,y1,y2,v;
- };
- bool cmp (data a,data other)
- {
- return a.x < other.x ;
- }
- vector<data>evnt;
- data pack(int _x,int _y1,int _y2,int _v)
- {
- data tmp;
- tmp.x=_x;
- tmp.y1=_y1;
- tmp.y2=_y2;
- tmp.v=_v;
- return tmp;
- }
- const int maxN = 3100000;
- pair<int,int> tree[maxN];
- int lft[maxN],rgt[maxN],lazy[maxN],last;
- void crt(int cn)
- {
- if(lft[cn]==0)
- {
- tree[last]=m_p(0,0);
- lft[cn]=last,lazy[last]=0,last++;
- lft[lft[cn]]=rgt[lft[cn]]=0;
- }
- if(rgt[cn]==0)
- {
- tree[last]=m_p(0,0);
- rgt[cn]=last,lazy[last]=0,last++;
- lft[rgt[cn]]=rgt[rgt[cn]]=0;
- }
- }
- int mx=0;
- void merge(int cn,int ln,int rn,ll carry)
- {
- if(lazy[cn]+carry==mx) tree[cn].ff=tree[ln].ff + tree[rn].ff;
- tree[cn].ss = max(tree[cn].ss,max(tree[ln].ss,tree[rn].ss));
- }
- void update(int cn,int st,int ed,int l,int r,int v,ll carry=0)
- {
- if(ed<l || st>r) return;
- mx=max(mx,tree[cn].ss);
- if(st>=l && ed<=r)
- {
- lazy[cn]+=v;
- tree[cn].ss+=carry+lazy[cn];
- if(lazy[cn]+carry==mx) tree[cn].ff=ed-st+1;
- else
- {
- if(st==ed) tree[cn].ff=0,tree[cn].ss=0;
- else
- {
- crt(cn);
- merge(cn,lft[cn],rgt[cn],carry);
- }
- }
- return;
- }
- int mid=(st+ed)>>1;
- crt(cn);
- update(lft[cn],st,mid,l,r,v,carry+lazy[cn]);
- update(rgt[cn],mid+1,ed,l,r,v,carry+lazy[cn]);
- merge(cn,lft[cn],rgt[cn],carry);
- mx=max(mx,tree[cn].ss);
- //cout<<st<<" "<<ed<<" -> "<<tree[cn].ss<<endl;
- }
- int main()
- {
- int kase,m,n;
- scanf("%d",&kase);
- for(int ks=1; ks<=kase; ks++)
- {
- scanf("%d",&n);
- int mny=1000000000,mxy=0,power;
- for(int i=1; i<=n; i++)
- {
- int x1,y1,x2,y2;
- scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
- scanf("%d",&power);
- evnt.pb(pack(x1,y1,y2-1,1*power)),evnt.pb(pack(x2,y1,y2-1,-1*power));
- mny=min(mny,min(y1,y2)),mxy=max(mxy,max(y1,y2));
- }
- sort(evnt.begin(),evnt.end(),cmp);
- int ind = 0, pre = evnt[0].x;
- // tree[1]=m_p(0,0);
- // lazy[1]=lft[1]=rgt[1]=0;
- memset(tree,0,sizeof(tree));
- memset(lft,0,sizeof(lft));
- memset(rgt,0,sizeof(rgt));
- last=2;
- while(ind < evnt.size() && evnt[ind].x == evnt[0].x )
- {
- //cout<<evnt[ind].y1<<" <begin> "<<evnt[ind].y2<<" "<<evnt[ind].v<<endl;
- update(1,mny,mxy,evnt[ind].y1,evnt[ind].y2,evnt[ind].v),ind++;
- }
- ll ans=0;
- while(ind < evnt.size() )
- {
- int cur=evnt[ind].x;
- ll delx = cur - pre,dely = tree[1].ff;
- pre=cur;
- ans += delx * dely ;
- while(ind < evnt.size() && evnt[ind].x == cur)
- {
- //cout<<evnt[ind].y1<<" <middle> "<<evnt[ind].y2<<" "<<evnt[ind].v<<endl;
- update(1,mny,mxy,evnt[ind].y1,evnt[ind].y2,evnt[ind].v),ind++;
- }
- }
- cout<<mx<<" "<<ans<<endl;
- tree[1]=m_p(0,0);
- lazy[1]=lft[1]=rgt[1]=0;
- last=2;ind=0;
- ans=0;
- while(ind < evnt.size() && evnt[ind].x == evnt[0].x )
- {
- //cout<<evnt[ind].y1<<" <begin> "<<evnt[ind].y2<<" "<<evnt[ind].v<<endl;
- update(1,mny,mxy,evnt[ind].y1,evnt[ind].y2,evnt[ind].v),ind++;
- }
- cout<<tree[1].ff<<endl;
- ans=0;
- while(ind < evnt.size() )
- {
- int cur=evnt[ind].x;
- ll delx = cur - pre,dely = tree[1].ff;
- pre=cur;
- ans += delx * dely ;
- while(ind < evnt.size() && evnt[ind].x == cur)
- {
- //cout<<evnt[ind].y1<<" <middle> "<<evnt[ind].y2<<" "<<evnt[ind].v<<endl;
- update(1,mny,mxy,evnt[ind].y1,evnt[ind].y2,evnt[ind].v),ind++;
- }
- }
- evnt.clear();
- printf("Case %d: %lld\n",ks,ans);
- }
- }
- /*
- 2
- 3
- 0 3 4 6 1
- 1 4 6 8 2
- 2 0 8 5 3
- 1
- 0 0 1000 1000 7
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement