Advertisement
Guest User

Untitled

a guest
Sep 16th, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.53 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int xmax,ymax,zmax,n,m,k;
  6.  
  7. map< int , map< int , pair< int ,int > > > pmap;
  8. vector< pair< int , map< int , pair< int ,int > > > > pvector;
  9. vector< pair< vector< pair< int , pair< int , int > > > , vector< pair< int , int > > > > tree;
  10. int oxl,oxr,oyl,oyr,ozl,ozr;
  11.  
  12. pair<int,int> comb(pair<int,int> p1,pair<int,int> p2)
  13. {
  14.     return make_pair(max(p1.first,p2.first),
  15.                      min(p1.second,p2.second));
  16. }
  17.  
  18. void build_y(int vx,int lxt, int rxt,int vy,int lyt, int ryt)
  19. {
  20.     if(lyt==ryt)
  21.     {
  22.         if(lxt==rxt)
  23.             tree[vx].second[vy]=tree[vx].first[lyt].second;
  24.         else
  25.         {
  26.             int sl,sr;
  27.             sl=0,sr=tree[vx*2+1].first.size()-1;
  28.             while(sr>sl)
  29.             {
  30.                 int sm=(sl+sr)/2;
  31.                 if(tree[vx*2+1].first[sm].first>=tree[vx].first[lyt].first)
  32.                     sr=sm;
  33.                 else
  34.                     sl=sm+1;
  35.             }
  36.             pair<int,int> res1=(tree[vx*2+1].first[sl].first==tree[vx].first[lyt].first)?
  37.                                (tree[vx*2+1].first[sl].second):
  38.                                 make_pair(0,(int)zmax+1);
  39.             sl=0,sr=tree[vx*2+2].first.size()-1;
  40.             while(sr>sl)
  41.             {
  42.                 int sm=(sl+sr)/2;
  43.                 if(tree[vx*2+2].first[sm].first>=tree[vx].first[lyt].first)
  44.                     sr=sm;
  45.                 else
  46.                     sl=sm+1;
  47.             }
  48.             pair<int,int> res2=(tree[vx*2+2].first[sl].first==tree[vx].first[lyt].first)?
  49.                                (tree[vx*2+2].first[sl].second):
  50.                                 make_pair(0,(int)zmax+1);
  51.             tree[vx].second[vy]=comb(res1,res2);
  52.         }
  53.     }
  54.     else
  55.     {
  56.         int myt=(lyt+ryt)/2;
  57.         build_y(vx,lxt,rxt,vy*2+1,lyt,myt);
  58.         build_y(vx,lxt,rxt,vy*2+2,myt+1,ryt);
  59.         tree[vx].second[vy]=comb(tree[vx].second[vy*2+1],tree[vx].second[vy*2+2]);
  60.     }
  61. }
  62.  
  63. void build_x(int vx,int lxt, int rxt)
  64. {
  65.     if(lxt==rxt)
  66.         tree[vx].first=vector< pair< int , pair< int , int > > >(pvector[lxt].second.begin(),pvector[lxt].second.end());
  67.     else
  68.     {
  69.         int mxt=(lxt+rxt)/2;
  70.         build_x(2*vx+1,lxt,mxt);
  71.         build_x(2*vx+2,mxt+1,rxt);
  72.         for(vector< pair< int , pair< int , int > > >::iterator i=tree[2*vx+1].first.begin(),j=tree[2*vx+2].first.begin();;)
  73.         {
  74.             if(i==tree[2*vx+1].first.end())
  75.             {
  76.                 for(;j!=tree[2*vx+2].first.end();j++)
  77.                     tree[vx].first.push_back(*j);
  78.                 break;
  79.             }
  80.             if(j==tree[2*vx+2].first.end())
  81.             {
  82.                 for(;i!=tree[2*vx+1].first.end();i++)
  83.                     tree[vx].first.push_back(*i);
  84.                 break;
  85.             }
  86.             if(i->first<j->first)
  87.             {
  88.                 tree[vx].first.push_back(*i);
  89.                 i++;
  90.             }
  91.             else if(j->first<i->first)
  92.             {
  93.                 tree[vx].first.push_back(*j);
  94.                 j++;
  95.             }
  96.             else
  97.             {
  98.                 tree[vx].first.push_back(make_pair(i->first,comb(i->second,j->second)));
  99.                 i++;
  100.                 j++;
  101.             }
  102.         }
  103.     }
  104.     tree[vx].second.resize(tree[vx].first.size()*4);
  105.     build_y(vx,lxt,rxt,0,0,tree[vx].first.size()-1);
  106. }
  107.  
  108. pair<int,int> get_y(int vx, int vy, int lyt, int ryt, int lyc, int ryc)
  109. {
  110.     if(lyc>ryc)
  111.         return make_pair(0,zmax+1);
  112.     if(lyc==lyt&&ryt==ryc)
  113.         return tree[vx].second[vy];
  114.     int myt=(lyt+ryt)/2;
  115.     return comb(get_y(vx,vy*2+1,lyt,myt,lyc,min(ryc,myt)),
  116.                 get_y(vx,vy*2+2,myt+1,ryt,max(lyc,myt+1),ryc));
  117. }
  118.  
  119. pair<int,int> get_x(int vx, int lxt, int rxt, int lxc, int rxc, int ly, int ry)
  120. {
  121.     if(lxc>rxc)
  122.         return make_pair(0,zmax+1);
  123.     if(lxc==lxt&&rxt==rxc)
  124.     {
  125.         int sl,sr;
  126.         sl=0,sr=tree[vx].first.size()-1;
  127.         while(sr>sl)
  128.         {
  129.             int sm=(sl+sr)/2;
  130.             if(tree[vx].first[sm].first>=ly)
  131.                 sr=sm;
  132.             else
  133.                 sl=sm+1;
  134.         }
  135.         int lyc=sl;
  136.         sl=0,sr=tree[vx].first.size()-1;
  137.         while(sr>sl)
  138.         {
  139.             int sm=(sl+sr+1)/2;
  140.             if(tree[vx].first[sm].first<=ry)
  141.                 sl=sm;
  142.             else
  143.                 sr=sm-1;
  144.         }
  145.         int ryc=sr;
  146.         return (tree[vx].first[lyc].first>=ly&&tree[vx].first[ryc].first<=ry)?
  147.                get_y(vx,0,0,tree[vx].first.size()-1,lyc,ryc):
  148.                make_pair(0,(int)zmax+1);
  149.     }
  150.     int mxt=(lxt+rxt)/2;
  151.     return comb(get_x(vx*2+1,lxt,mxt,lxc,min(rxc,mxt),ly,ry),
  152.                 get_x(vx*2+2,mxt+1,rxt,max(lxc,mxt+1),rxc,ly,ry));
  153. }
  154.  
  155. int main()
  156. {
  157.     scanf("%d%d%d%d%d%d",&xmax,&ymax,&zmax,&n,&m,&k);
  158.     oxl=xmax;
  159.     oxr=1;
  160.     oyl=ymax;
  161.     oyr=1;
  162.     ozl=zmax;
  163.     ozr=1;
  164.     for(int i=0;i<n;i++)
  165.     {
  166.         int x,y,z;
  167.         scanf("%d%d%d",&x,&y,&z);
  168.         oxl=min(oxl,x);
  169.         oxr=max(oxr,x);
  170.         oyl=min(oyl,y);
  171.         oyr=max(oyr,y);
  172.         ozl=min(ozl,z);
  173.         ozr=max(ozr,z);
  174.     }
  175.     for(int i=0;i<m;i++)
  176.     {
  177.         int x,y,z;
  178.         scanf("%d%d%d",&x,&y,&z);
  179.         if(oxl<=x&&x<=oxr&&oyl<=y&&y<=oyr&&ozl<=z&&z<=ozr)
  180.         {
  181.             printf("INCORRECT\n");
  182.             exit(0);
  183.         }
  184.         map< int , pair< int ,int > >::iterator it=pmap[x].insert(make_pair(y,make_pair(0,zmax+1))).first;
  185.         if(z<=ozr)
  186.             it->second.first=max(it->second.first,z);
  187.         if(z>=ozl)
  188.             it->second.second=min(it->second.second,z);
  189.     }
  190.     printf("CORRECT\n");
  191.     if(m>0)
  192.     {
  193.         pvector=vector< pair< int , map< int , pair< int ,int > > > >(pmap.begin(),pmap.end());
  194.         tree.resize(pvector.size()*4);
  195.         build_x(0,0,pvector.size()-1);
  196.     }
  197.     for(int i=0;i<k;i++)
  198.     {
  199.         int x,y,z;
  200.         scanf("%d%d%d",&x,&y,&z);
  201.         if(oxl<=x&&x<=oxr&&oyl<=y&&y<=oyr&&ozl<=z&&z<=ozr)
  202.         {
  203.             printf("OPEN\n");
  204.             continue;
  205.         }
  206.         if(m==0)
  207.         {
  208.             printf("UNKNOWN\n");
  209.             continue;
  210.         }
  211.         bool closed=false;
  212.         for(int ii=0;ii<=1;ii++)
  213.             for(int jj=0;jj<=1;jj++)
  214.             {
  215.                 if(closed)
  216.                     break;
  217.                 int i=oxl+ii*(oxr-oxl);
  218.                 int j=oyl+jj*(oyr-oyl);
  219.                 int lx=min(x,i),rx=max(x,i);
  220.                 int sl,sr;
  221.                 sl=0,sr=pvector.size()-1;
  222.                 while(sr>sl)
  223.                 {
  224.                     int sm=(sl+sr)/2;
  225.                     if(pvector[sm].first>=lx)
  226.                         sr=sm;
  227.                     else
  228.                         sl=sm+1;
  229.                 }
  230.                 int lxc=sl;
  231.                 sl=0,sr=pvector.size()-1;
  232.                 while(sr>sl)
  233.                 {
  234.                     int sm=(sl+sr+1)/2;
  235.                     if(pvector[sm].first<=rx)
  236.                         sl=sm;
  237.                     else
  238.                         sr=sm-1;
  239.                 }
  240.                 int rxc=sr;
  241.                 if(pvector[lxc].first>=lx&&pvector[rxc].first<=rx)
  242.                 {
  243.                     pair<int,int> p=get_x(0,0,pvector.size()-1,lxc,rxc,min(y,j),max(y,j));
  244.                     if(min({z,ozl,ozr})<=p.first||max({z,ozl,ozr})>=p.second)
  245.                         closed=true;
  246.                 }
  247.             }
  248.         if(closed)
  249.             printf("CLOSED\n");
  250.         else
  251.             printf("UNKNOWN\n");
  252.     }
  253. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement