fork(3) download
  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
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc