fork(4) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int kk=-1e9+7;
  4. vector<int>SegTree(4*100005,kk);
  5. vector<int>SegTree2(4*100005,kk);
  6. bool comp(pair<int,pair<int,int>>&abc,pair<int,pair<int,int>>&def)
  7. {
  8.     if(abc.first==def.first)
  9.     {
  10.         return abc.second.first<def.second.first;
  11.     }
  12.     return abc.first<def.first;
  13. }
  14. void update(int start,int end,int Tree_index,int qstart,int qend,int val)
  15. {
  16.     if(end<qstart || qend<start)
  17.     {
  18.         return;
  19.     }
  20.     if(qstart<=start && qend>=end)
  21.     {
  22.         SegTree[Tree_index]=val;
  23.         return;
  24.     }
  25.     int mid=(start+end)/2;
  26.     update(start,mid,2*Tree_index+1,qstart,qend,val);
  27.     update(mid+1,end,2*Tree_index+2,qstart,qend,val);
  28. }
  29. void update2(int start,int end,int Tree_index,int qstart,int qend,int val)
  30. {
  31.     if(end<qstart || qend<start)
  32.     {
  33.         return;
  34.     }
  35.     if(qstart<=start && qend>=end)
  36.     {
  37.         SegTree2[Tree_index]=val;
  38.         return;
  39.     }
  40.     int mid=(start+end)/2;
  41.     update2(start,mid,2*Tree_index+1,qstart,qend,val);
  42.     update2(mid+1,end,2*Tree_index+2,qstart,qend,val);
  43. }
  44. int query(int start,int end,int Tree_index,int qstart,int qend)
  45. {
  46.     if(end<qstart || qend<start)
  47.     {
  48.         return kk;
  49.     }
  50.     if(qstart<=start && qend>=end)
  51.     {
  52.         return SegTree[Tree_index];
  53.     }
  54.     int mid=(start+end)/2;
  55.     return max(query(start,mid,2*Tree_index+1,qstart,qend),query(mid+1,end,2*Tree_index+2,qstart,qend));
  56. }
  57. int query2(int start,int end,int Tree_index,int qstart,int qend)
  58. {
  59.     if(end<qstart || qend<start)
  60.     {
  61.         return kk;
  62.     }
  63.     if(qstart<=start && qend>=end)
  64.     {
  65.         return SegTree2[Tree_index];
  66.     }
  67.     int mid=(start+end)/2;
  68.     return max(query2(start,mid,2*Tree_index+1,qstart,qend),query2(mid+1,end,2*Tree_index+2,qstart,qend));
  69. }
  70. int main()
  71. {
  72.     int test;
  73.     cin>>test;
  74.     while(test--)
  75.     {
  76.     int row,col;
  77.     cin>>row>>col;
  78.     vector<vector<int>>input(row,vector<int>(col));
  79.     vector<vector<int>>output(row,vector<int>(col));
  80.     vector<pair<int,pair<int,int>>>temp;
  81.     for(int i=0;i<row;++i)
  82.     {
  83.         for(int j=0;j<col;++j)
  84.         {
  85.             cin>>input[i][j];
  86.             temp.push_back({input[i][j],{i,j}});
  87.         }
  88.     }
  89.     sort(temp.begin(),temp.end(),comp);
  90.     int pk=1,prev;
  91.     for(int i=0;i<temp.size();++i)
  92.     {
  93.         int x=temp[i].second.first,y=temp[i].second.second;
  94.         int curr_row_start=col*x+1;
  95.         int curr_row_end=col*(x+1);
  96.         int curr_col_start=row*y+1;
  97.         int curr_col_end=row*(y+1);
  98.         //cout<<"++++++++++++++++++++++++++++++++++++++"<<endl;
  99.         //cout<<curr_row_start<<" :: "<<curr_row_end<<endl;
  100.         //cout<<curr_col_start<<" :: "<<curr_col_end<<endl;
  101.         //cout<<temp[i].first<<" index "<<x<<" :: "<<y<<endl;
  102.         if(i==0)
  103.         {
  104.             output[x][y]=pk;
  105.             update(1,row*col,0,curr_row_start,curr_row_end,pk);
  106.             update2(1,row*col,0,curr_col_start,curr_col_end,pk);
  107.             prev=temp[i].first;
  108.         }
  109.         else
  110.         {
  111.             if(temp[i].first==prev)
  112.             {
  113.                 update(1,row*col,0,curr_row_start,curr_row_end,pk);
  114.                 update2(1,row*col,0,curr_col_start,curr_col_end,pk);
  115.                 output[x][y]=pk;
  116.             }
  117.             else
  118.             {
  119.                 int ss=query(1,row*col,0,curr_row_start,curr_row_end);
  120.               //  cout<<"ss "<<ss<<endl;
  121.                 int zz=query2(1,row*col,0,curr_col_start,curr_col_end);
  122.                 //cout<<"zz "<<zz<<endl;
  123.                 if(ss==zz && ss==kk)
  124.                 {
  125.                     update(1,row*col,0,curr_row_start,curr_row_end,pk);
  126.                     update2(1,row*col,0,curr_col_start,curr_col_end,pk);
  127.                     output[x][y]=pk;
  128.                 }
  129.                 else
  130.                 {
  131.                     pk=max(ss,zz)+1;
  132.                     output[x][y]=pk;
  133.                     update(1,row*col,0,curr_row_start,curr_row_end,pk);
  134.                     update2(1,row*col,0,curr_col_start,curr_col_end,pk);
  135.                 }
  136.                 prev=temp[i].first;
  137.             }
  138.         }
  139.         //cout<<output[x][y]<<endl;
  140.     }
  141.   //  cout<<"+++++++++++++++++++++++++"<<endl;
  142.     for(int i=0;i<row;++i)
  143.     {
  144.         for(int j=0;j<col;++j)
  145.         {
  146.             cout<<output[i][j]<<" ";
  147.         }
  148.         cout<<endl;
  149.     }
  150.     }
  151.     return 0;
  152. }
  153.  
Runtime error #stdin #stdout #stderr 0s 18368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/Bs911f
language:
C++14 (gcc 8.3)
created:
4 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!