Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct xseg {int x,miny,maxy; bool open;};
- struct yseg {int y,wx1,wx2; bool down;};
- vector <xseg> dx;
- vector <yseg> dy;
- vector <int> t;
- vector <int> tmax;
- vector <int> wmax;
- bool com(yseg a,yseg b) {
- return a.y<b.y;}
- bool com1(xseg a,xseg b) {
- if (a.x!=b.x) return a.x<b.x;
- if (a.open) return true;
- return false;}
- int min (int a,int b) {return (a<b?a:b);}
- int max (int a,int b) {return (a>b?a:b);}
- int n;
- void update(int v,int tL,int tR,int l,int r,int add){
- if (l>r) return;
- if (tR==tL|(tL==l&tR==r)) {t[v]+=add;tmax[v]+=add;return;}
- int tM=(tL+tR)/2;
- update(v*2,tL,tM,l,min(r,tM),add);
- update(v*2+1,tM+1,tR,max(l,tM+1),r,add);
- tmax[v]=-1;
- if (tmax[v]<tmax[v*2+1]) {tmax[v]=tmax[v*2+1]+t[v];wmax[v]=wmax[v*2+1];}
- if (tmax[v]<tmax[v*2]) {tmax[v]=tmax[v*2]+t[v];wmax[v]=wmax[v*2];}
- }
- pair <int,int> getmax() {
- return make_pair(tmax[1],wmax[1]);
- }
- int main() {
- freopen("windows.in","r",stdin);
- //freopen("windows.out","w",stdout);
- scanf("%d\n",&n);
- for (int i=1;i<=n;i++)
- {
- int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
- xseg z; z.x=x1; z.open=true;
- dx.push_back(z);
- z.x=x2; z.open=false;
- dx.push_back(z);
- yseg v; v.y=y1; v.down=true; v.wx1=(int)dx.size()-1; v.wx2=v.wx1-1;
- dy.push_back(v);
- v.y=y2; v.down=false; v.wx1=(int)dx.size()-1; v.wx2=v.wx1-1;
- dy.push_back(v);
- }
- sort(dy.begin(),dy.end(),com);
- int down[dy.size()]; int up[dy.size()];
- down[0]=0;
- for (int i=1;i<(int)dy.size();i++)
- if (dy[i].y==dy[i-1].y) down[i]=down[i-1]; else down[i]=i;
- up[dy.size()-1]=dy.size()-1;
- for (int i=(int)dy.size()-2;i>=0;i--)
- if (dy[i].y==dy[i+1].y) up[i]=up[i+1]; else up[i]=i;
- for (int i=0;i<(int)dy.size();i++)
- if (dy[i].down) {dx[dy[i].wx1].miny=down[i]; dx[dy[i].wx2].miny=down[i];}
- else {dx[dy[i].wx1].maxy=up[i]; dx[dy[i].wx2].maxy=up[i];}
- sort(dx.begin(),dx.end(),com1);
- //подготовка
- int p[30]; p[0]=1;
- for (int i=1;i<=30;i++)
- { p[i]=p[i-1]*2; if (p[i]>=(int)dy.size()) {n=p[i];break;} }
- t.resize(2*n+3,0); tmax.resize(2*n+3,0); wmax.resize(2*n+3);//n до степени 2-ки
- for (int i=n;i<=2*n-1;i++) wmax[i]=i;
- for (int i=1;i<n;i++) wmax[i]=wmax[2*i];
- // for (int i=0;i<(int)dx.size();i++)
- // printf("%d to %d = %d\n",dx[i].miny+n,dx[i].maxy+n,dx[i].open);
- int xm,ym,max=-1;
- for (int i=0;i<(int)dx.size();i++)
- { int add; if (dx[i].open) add=1; else add=-1;
- update(1,n,2*n-1,dx[i].miny+n,dx[i].maxy+n,add);
- pair <int,int> k=getmax();
- if (k.first>max) {xm=dx[i].x;ym=dy[k.second-n].y;max=k.first;}
- // for (int j=dx[i].miny;j<=dx[i].maxy;j++)
- // {t[j]+=add; if (t[j]>max) {xm=dx[i].x;ym=dy[j].y; max=t[j];}}
- // printf("getmax=%d\n",getmax().first);
- // for (int j=1;j<=2*n-1;j++) printf("t[%d]=%d tmax[%d]=%d wmax[%d]=%d\n",j,t[j],j,tmax[j],j,wmax[j]);
- // printf("\n");
- }
- printf("%d\n%d %d",max,xm,ym);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement