Advertisement
Josif_tepe

Untitled

Mar 6th, 2023
1,044
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <stack>
  8. #include <queue>
  9. #include <fstream>
  10. using namespace std;
  11. typedef int ll;
  12.  
  13. set<ll> smaller_values, greater_values;
  14. int n, k;
  15.    
  16. void insert_value(ll & x) {
  17.     ll max_in_smaller_values = *smaller_values.rbegin();
  18.      
  19.     if(max_in_smaller_values < x) {
  20.         greater_values.insert(x);
  21.          
  22.         if(greater_values.size() > k / 2) {
  23.             ll min_in_greater = *greater_values.begin();
  24.             smaller_values.insert(min_in_greater);
  25.             greater_values.erase(greater_values.find(min_in_greater));
  26.         }
  27.     }
  28.     else {
  29.         smaller_values.insert(x);
  30.          
  31.         if(smaller_values.size() > (k + 1) / 2) {
  32.             ll tmp_max_in_smaller = *smaller_values.rbegin();
  33.             greater_values.insert(tmp_max_in_smaller);
  34.             smaller_values.erase(smaller_values.find(tmp_max_in_smaller));
  35.         }
  36.     }
  37.      
  38. }
  39. void remove_element(ll & x) {
  40.     if(greater_values.find(x) != greater_values.end()) {
  41.         greater_values.erase(greater_values.find(x));
  42.     }
  43.     else if(smaller_values.find(x) != smaller_values.end()) {
  44.         smaller_values.erase(smaller_values.find(x));
  45.     }
  46.      
  47.     if(smaller_values.empty()) {
  48.         ll min_in_greater = *greater_values.begin();
  49.         smaller_values.insert(min_in_greater);
  50.         greater_values.erase(greater_values.find(min_in_greater));
  51.     }
  52.      
  53. }
  54. ll mat[888][888];
  55. int main(){
  56.     ios_base::sync_with_stdio(false);
  57. //    ifstream cinx("input.txt");
  58.     cin >> n >> k;
  59.     ll ss = 2e9;
  60.     for(int i = 0; i < n; i++) {
  61.         for(int j = 0; j < n; j++) {
  62.             cin >> mat[i][j];
  63.             ss = min(ss, mat[i][j]);
  64.         }
  65.          
  66.     }
  67.     if(k == 1) {
  68.         cout << ss << endl;
  69.         return 0;
  70.     }
  71.     int K = k;
  72.     k *= k;
  73.     smaller_values.insert(mat[0][0]);
  74.      
  75.     for(int i = 0; i < K; i++) {
  76.         for(int j = 0; j < K; j++) {
  77.             if(i == 0 and j == 0) continue;
  78.             insert_value(mat[i][j]);
  79.         }
  80.     }
  81.     ll result = *smaller_values.rbegin();
  82.     int i1 = 0, i2 = K - 1;
  83.     int j1 = 0, j2 = K - 1;
  84.      
  85.     int dir = 1;
  86.     while(i2 < n) {
  87.         if(dir == 1) {
  88.             result = min(result, *smaller_values.rbegin());
  89.            
  90.            
  91.             if(j2 + 1 < n) {
  92.                 for(int i = i1; i <= i2; i++) {
  93.                     remove_element(mat[i][j1]);
  94.                 }
  95.                 j1++;
  96.                 j2++;
  97.                 for(int i = i1; i <= i2; i++) {
  98.                     insert_value(mat[i][j2]);
  99.                 }
  100.                 result = min(result, *smaller_values.rbegin());
  101.             }
  102.             else {
  103.                 dir = -1;
  104.                 for(int j = j1; j <= j2; j++) {
  105.                     remove_element(mat[i1][j]);
  106.                 }
  107.  
  108.                 i1++;
  109.                 i2++;
  110.                 if(i2 < n) {
  111.                     for(int j = j1; j <= j2; j++) {
  112.                         insert_value(mat[i2][j]);
  113.                     }
  114.                     result = min(result, *smaller_values.rbegin());
  115.                 }
  116.             }
  117.         }
  118.         else {
  119.             result = min(result, *smaller_values.rbegin());
  120.              
  121.      
  122.             if(j1 - 1 >= 0) {
  123.                 for(int i = i1; i <= i2; i++) {
  124.                     remove_element(mat[i][j2]);
  125.                 }
  126.                 j1--;
  127.                 j2--;
  128.                 for(int i = i1; i <= i2; i++) {
  129.                     insert_value(mat[i][j1]);
  130.                 }
  131.             }
  132.             else {
  133.                 dir = 1;
  134.                 for(int j = j1; j <= j2; j++) {
  135.                     remove_element(mat[i1][j]);
  136.                 }
  137.                 i1++;
  138.                 i2++;
  139.                 if(i2 < n) {
  140.                     for(int j = j1; j <= j2; j++) {
  141.                         insert_value(mat[i2][j]);
  142.                     }
  143.                     result = min(result, *smaller_values.rbegin());
  144.                 }
  145.             }
  146.         }
  147.     }
  148.     cout << result << endl;
  149.      
  150.     return 0;
  151. }
  152.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement