fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <string>
  6. #include <iomanip>
  7. #include <cmath>
  8. #include <ctime>
  9. #include <numeric>
  10. #include <bitset>
  11. #define endl '\n'
  12. #define ll long long
  13. #define all(n) n.begin() , n.end( )
  14. #define vi vector<int>
  15. #define vvi vector<vi>
  16. #define int long long
  17. #define pii pair<int,int>
  18. #define vpii vector<pair<int,int>>
  19. #define mii map<int,int>
  20. #define si set<int>
  21. #define input(v,n) for(int i = 0 ; i< n ; i++) cin >> v[i]
  22. #define output(v)  for(auto it : v) cout << it << endl;
  23. #define IS_POWER_OF_TWO(n) ((n) && !((n) & ((n) - 1)))
  24. #define bug(...) _f (#__VA_ARGS__,__VA_ARGS__)
  25. #define lb(x,w,z) for(int x=w;x<z;x++)
  26. #define FOR (x,y) for(auto x:y)
  27. #define revlop(a,b,c) for(int a=b;a>=c;a--)
  28.  
  29. // #include <ext/pb_ds/assoc_container.hpp>
  30. // #include <ext/pb_ds/tree_policy.hpp>
  31. // using namespace std;
  32. // using namespace __gnu_pbds;
  33. // template<class t> using ordered_multiset = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
  34. //---------------------------------------------------------------
  35.  
  36. int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
  37. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  38.  
  39. using namespace std;
  40. void fast() {
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.     cout.tie(NULL);
  44. }
  45.  
  46. // const ll  N= 2e6+5;
  47. // ll  pre[N],pre2[N],next_arr[N],arr[N],bb[N] ;
  48. /*
  49.  
  50. ll sqrtt(ll n){
  51. ll l{},r= 1000000000+1,mid;
  52. while(r-l>1){
  53.     mid = l+(r-l)/2;
  54.     if( mid * mid > n )r=mid;
  55.     else l =mid;
  56. }
  57. return l;
  58. }
  59.  
  60. ll lcm ( ll a , ll b)
  61. {
  62.     return (a*b)/gcd(a,b);
  63. }
  64.  
  65. ll fast_power(ll a,ll b , int mod){
  66.     ll ans=1;
  67.     while(b){
  68.     if(b&1){
  69.         ans*=a;
  70.         ans%=mod;
  71.     }
  72.     a*=a;
  73.     a%=mod;
  74.     b = (b>>1);
  75. }
  76. return ans;
  77. }
  78. /*
  79. ll gcd ( ll a, ll b)
  80. {
  81.     if ( b == 0 )
  82.         return a;
  83.     return gcd(b, a%b);
  84. }
  85. vector<int> vis(N);
  86. vector<int> prime(N ) ;
  87. void get_prime(){
  88.     prime[0] = 0 , prime[1] = 1 ;
  89.     for (int i = 2 ; i<= N ; i++){
  90.         if ( !prime[i]  ){
  91.             for (int j = i ; j <= N ; j+=i)
  92.                 prime[j] = i ;
  93.  
  94.         }
  95.     }
  96. }
  97.  
  98. vi prims(N);
  99. void seive(int n ){
  100.     prims[0] = prims[1] = 1;
  101.     for (int  i = 2 ; i* i <= n ; i++){
  102.         if ( !prims[i] ){
  103.             prims[i]  = 0 ;
  104.             for (int j = 2*i ; j <= n ; j+=i ){
  105.                 prims[j] = 1;
  106.             }
  107.         }
  108.     }
  109. }
  110.  
  111. vector<int> prim_fac(ll n ){
  112.     vector<int> v;
  113.     for (int i = 2 ; i*i <= n ;i ++ ){
  114.         while (n != 1 ){
  115.             if ( n % i == 0 ){
  116.                 n/=i;
  117.                 v.push_back(i);
  118.             }
  119.             else break;
  120.         }
  121.     }
  122.     return v;
  123. }
  124.  
  125. bool is_prime(int n)
  126. {
  127.     bool isprime = true;
  128.     if ( n == 1)
  129.         return false;
  130.     for (int i = 2 ; i * i <= n ; i++)
  131.     {
  132.         if ( n %i == 0 )
  133.             isprime = false;
  134.     }
  135.     return isprime;
  136. }*/
  137.  
  138.  
  139.  
  140. const  ll oo = 1e18+2 , mod = 1e9+7 ;
  141. const  int N = 2e4+5 , M = 1e6+5;
  142.  
  143.  
  144.  
  145. int ans = 0 ;
  146. map<pair<int,int>, int >vis;
  147. map<int , map<int,int>> mp;
  148. map<int,int> calc;
  149.  
  150. bool flag = false;
  151.  
  152. int s, n, m ;
  153.  
  154. int dxx[] = {0, 0, 1, -1};
  155. int dyy[] = {1, -1, 0, 0};
  156.  
  157. bool valid ( int i , int j ){
  158.     return i>= 0 && i<n && j >= 0 && j<m;
  159. }
  160.  
  161. int cont = 0;
  162.  
  163. void dfs (int mid ,int i , int j  ,   vector<vector<ll>> &grid ){
  164.     vis[{i,j}] = 1 ;
  165.     cont ++;
  166.     if ( cont >= s ){
  167.         ans = max ( mid , ans );
  168.         flag = true;
  169.         return;
  170.     }
  171.     calc[mid] = cont;
  172.     if ( !flag ){
  173.         for (int k = 0 ;  k < 4 ; k ++ ){
  174.             int x = i + dxx[k];
  175.             int y = j + dyy[k];
  176.             if ( valid( x, y) && grid[x][y] >= mid && !vis[{x , y}]  ){
  177.                 dfs( mid , x, y, grid);
  178.             }
  179.          }
  180.     }
  181. }
  182.  
  183. void solve( ){
  184.     cin  >> s >> n >> m ;
  185.     set<int>st;
  186.     int mx = 0;
  187.     vector<vector<ll>>grid(n+5,vector<ll>(m+5,0));
  188.     map<int, vector<pii>> mp;
  189.     vector<int > v;
  190.     for (int i =0  ; i < n;i ++ ){
  191.         for (int j = 0 ; j < m; j ++ ){
  192.             cin >> grid[i][j];
  193.             st.insert(grid[i][j]);
  194.             mx = max ( mx , grid[i][j]);
  195.             mp[grid[i][j]].push_back( { i , j } );
  196.         }
  197.     }
  198.     for (auto it : st ){
  199.         v.push_back((it));
  200.     }
  201.     int l = 1 , r = mx ;
  202.     while ( r >= l ){
  203.         int mid = ( r + l ) /2 ;
  204.         if ( mid <= ( *st.begin())){
  205.             l  = mid + 1 ;
  206.             ans = max ( l -1 , ans  ) ;
  207.         }
  208.         else {
  209.             auto it = st.lower_bound(mid);
  210.             for (auto i = it ; i != st.end() ; i++ ){
  211.                 int val = *i;
  212.                 if ( flag){
  213.                     break;
  214.                 }
  215.                 for (auto it : mp[val]){ // map<int , vector<pair>> { ( 1, 2 ), , ( 3,4) }
  216.                     if ( !flag && !vis[ it] ){
  217.                         dfs( mid ,  it.first , it.second  , grid  );
  218.                         cont = 0 ;
  219.                     }
  220.                     else {
  221.                         break;
  222.                     }
  223.                 }
  224.             }
  225.             vis.clear();
  226.             if( flag ){
  227.                 l = mid +  1 ;
  228.             }
  229.             else {
  230.                 r = mid - 1;
  231.             }
  232.             flag = false;
  233.         }
  234.     }
  235.     cout << ans << endl;
  236.  
  237. }
  238.  
  239.  
  240. signed main( )
  241. {
  242.     //   freopen("input.txt","r",stdin);
  243.     //  freopen("output.txt","w",stdout);
  244. //#endif
  245.     fast();
  246.     int t =1;
  247.     clock_t w =clock();
  248.     // cin >> t ;
  249.     while ( t -- ){
  250.         solve();
  251.     }
  252.  
  253. // cerr << "Run time : " << ((double) (clock() - w) / CLOCKS_PER_SEC);
  254. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/eXxZoe
language:
C++ (gcc 8.3)
created:
10 days 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!