fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define f first
  5. #define s second
  6. #define PI acos(-1)
  7. #define CS ios_base::sync_with_stdio(0);cin.tie(0);
  8. using namespace std;
  9.  
  10. int mn[1 << 22],mx[1 << 22],lazy[1 << 22];
  11.  
  12. void propagate(int i,int l,int r)
  13. {
  14.     if(!lazy[i])return;
  15.     mn[i]+=lazy[i];
  16.     mx[i]+=lazy[i];
  17.     if(l!=r)
  18.     {
  19.         lazy[i*2]+=lazy[i];
  20.         lazy[i*2+1]+=lazy[i];
  21.     }
  22.     lazy[i]=0;
  23. }
  24.  
  25. void update(int i,int l,int r,int a,int b,int v)
  26. {
  27.     propagate(i,l,r);
  28.     if(l>b || r<a)return;
  29.     if(l>=a & r<=b)
  30.     {
  31.         lazy[i]+=v;
  32.         propagate(i,l,r);
  33.         return;
  34.     }
  35.     int mid = (l+r) >>1;
  36.     update(i*2, l,mid,a,b,v);
  37.     update(i*2 +1, mid+1,r,a,b,v);
  38.     mn[i]=min(mn[i*2],mn[i*2+1]);
  39.     mx[i]=max(mx[i*2],mx[i*2+1]);
  40. }
  41.  
  42. int getMin(int i,int l,int r,int a,int b)
  43. {
  44.     propagate(i,l,r);
  45.     if(l>b|| r<a)return 1e9;
  46.     if(l>=a &&r<=b)return mn[i];
  47.     int mid=(l+r)>>1;
  48.     return min(getMin(i*2,l,mid,a,b),getMin(i*2+1,mid+1,r,a,b));
  49. }
  50.  
  51. int getMax(int i,int l,int r,int a,int b)
  52. {
  53.     propagate(i,l,r);
  54.     if(l>b|| r<a)return -1e9;
  55.     if(l>=a &&r<=b)return mx[i];
  56.     int mid=(l+r)>>1;
  57.     return max(getMax(i*2,l,mid,a,b),getMax(i*2+1,mid+1,r,a,b));
  58. }
  59.  
  60. struct Rect
  61. {
  62.     //top lef=(x1,y1) , bottom rihjt =(x2,y2)
  63.     int x1,x2,y1,y2;
  64.     Rect(int x11,int x22,int y11,int y22)
  65.     {
  66.         x1=x11;
  67.         y1=y11;
  68.         x2=x22;
  69.         y2=y22;
  70.     }
  71. };
  72.  
  73. vector<Rect>rects;
  74.  
  75. void compress()
  76. {
  77.     map<int,int>xs,ys;
  78.     for(int i=0; i<rects.size(); i++)
  79.     {
  80.         xs[rects[i].x1]=0;
  81.         xs[rects[i].x2]=0;
  82.         ys[rects[i].y1]=0;
  83.         ys[rects[i].y2]=0;
  84.     }
  85.     int tmp=1;
  86.     for(map<int,int>::iterator it = xs.begin(); it!=xs.end(); it++)
  87.         it->s=tmp++;
  88.     tmp=1;
  89.     for(map<int,int>::iterator it = ys.begin(); it!=ys.end(); it++)
  90.         it->s=tmp++;
  91.     for(int i=0; i<rects.size(); i++)
  92.     {
  93.         rects[i].x1=xs[rects[i].x1];
  94.         rects[i].x2=xs[rects[i].x2];
  95.         rects[i].y1=ys[rects[i].y1];
  96.         rects[i].y2=ys[rects[i].y2];
  97.     }
  98. }
  99.  
  100. bool comp(Rect a,Rect b)
  101. {
  102.     return a.y1<b.y1;
  103. }
  104.  
  105. bool doubleBorder(int x1,int x2)
  106. {
  107.     if(abs(getMin(1,0,(1<<19),x1,x1)-getMin(1,0,(1<<19),x1-1,x1-1))>1)return 1;
  108.     if(abs(getMin(1,0,(1<<19),x2,x2)-getMin(1,0,(1<<19),x2+1,x2+1))>1)return 1;
  109.     return 0;
  110. }
  111.  
  112. bool sweep()
  113. {
  114.     sort(rects.begin(),rects.end(),comp);
  115.     memset(lazy,0,sizeof lazy);
  116.     memset(mx,0,sizeof mx);
  117.     memset(mn,0,sizeof mn);
  118.  
  119.     //{y2,{x1,X2}}
  120.     set<pair<int,pair<int,int> > >er;
  121.     for(int i=0; i<rects.size(); i++)
  122.     {
  123.         while(er.size()&&er.begin()->f <= rects[i].y1)
  124.         {
  125.             int x1=er.begin()->s.f,x2=er.begin()->s.s;
  126.             update(1, 0, (1 << 19), x1, x2, -1);
  127.             if((getMin(1,0,(1<<19),x1,x2)!=getMax(1,0,(1<<19),x1,x2))||
  128.                                             doubleBorder(x1,x2))return 0;
  129.             er.erase(er.begin());
  130.         }
  131.  
  132.  
  133.         update(1,0,(1 << 19),rects[i].x1,rects[i].x2,1);
  134.         er.insert({rects[i].y2+1,{rects[i].x1,rects[i].x2}});
  135.         if((getMin(1,0,(1<<19),rects[i].x1,rects[i].x2)!=getMax(1,0,(1<<19),rects[i].x1,rects[i].x2))||doubleBorder(rects[i].x1,rects[i].x2))return 0;
  136.     }
  137.     return 1;
  138. }
  139.  
  140. bool isvalid()
  141. {
  142.     compress();
  143.     if(!sweep())return 0;
  144.     for(int i=0; i<rects.size(); i++)
  145.     {
  146.         swap(rects[i].x1,rects[i].y1);
  147.         swap(rects[i].x2,rects[i].y2);
  148.     }
  149.     if(!sweep())return 0;
  150.     return 1;
  151.  
  152. }
  153. int main()
  154. {
  155.     CS;
  156.     int n;
  157.     cin>>n;
  158.     //{{x,y},indx}
  159.     vector<pair<pair<int,int>,int> >a(2*n),input;
  160.     for(int i=0; i<2*n; i++)cin>>a[i].f.f>>a[i].f.s, a[i].s=i;
  161.     input =a;
  162.     sort(a.begin(),a.end());
  163.     //{y,indx}
  164.     set<pair<int,int> >st;
  165.     vector<int>res(n);
  166.     for(int i=0; i<2*n; i++)
  167.     {
  168.         int x=a[i].f.f,y=a[i].f.s,ind=a[i].s;
  169.         if(ind < n)
  170.         {
  171.             st.insert({y,ind});
  172.         }
  173.         else
  174.         {
  175.             set<pair<int,int> >::iterator it = st.lower_bound({y,-1});
  176.             if(it==st.begin())return cout<<"syntax error", 0;
  177.             it--;
  178.             res[it->s]=ind;
  179.             rects.push_back(Rect(input[it->s].f.f,x,it->f,y));
  180.             st.erase(it);
  181.         }
  182.     }
  183.  
  184.     if(!isvalid())cout<<"syntax error";
  185.     else
  186.     {
  187.         for(int i=0; i<n; i++)cout<<res[i]-n+1<<"\n";
  188.     }
  189.     return 0;
  190. }
Success #stdin #stdout 0.01s 64408KB
comments (?)
stdin
copy 
2
4 7
9 8
14 17
19 18
stdout
copy 
2
1
https://ideone.com/FLbHAL
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!