oj.uz

답안 #922361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922361 2024-02-05T12:36:59 Z thunopro 최솟값 배열 (IZhO11_hyper) C++14
100 / 100
 258 ms 65108 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 200009 
#define ll long long 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 

const int mod = 1e9+7; 
const int INF = 1e9; 

typedef vector<int> vi; 
typedef pair<int,int> pii;
typedef vector<pii> vii;  
typedef vector<ll> vl;

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a > mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

template <typename T> void chkmin ( T &a , T b ) { if ( a > b ) a = b ; }
template <typename T> void chkmax ( T &a , T b ) { if ( a < b ) a = b ; }

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ;
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ;
}
const int nm = 40 ; 
int n , m ; 
int a [nm][nm][nm][nm] ;
int f1 [nm][nm][nm][nm] , f2 [nm][nm][nm][nm] , f3 [nm][nm][nm][nm] , f4 [nm][nm][nm][nm] ;  

deque <int> dq ; 

int main () 
{
	ios_base::sync_with_stdio(0); 
	cin.tie(0);cout.tie(0); 
//	rf () ; 
	cin >> n >> m ; 
	
	for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= n ; j ++ ) for ( int k = 1 ; k <= n ; k ++ ) for ( int l = 1 ; l <= n ; l ++ ) cin >> a [i][j][k][l] ; 
	for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= n ; j ++ ) for ( int k = 1 ; k <= n ; k ++ )
	{
		dq.clear() ; 
		for ( int l = 1 ; l <= n ; l ++ ) 
		{
			if ( !dq.empty() && dq.front() + m <= l ) dq.pop_front(); 
			while ( !dq.empty() && a[i][j][k][l] <= a[i][j][k][dq.back()]) dq.pop_back(); 
			dq.pb(l); 
			if ( l >= m ) f1 [i][j][k][l] = a [i][j][k][dq.front()] ; 
		}
	}
	
	for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= n ; j ++ ) for ( int l = m ; l <= n ; l ++ )
	{
		dq.clear() ; 
		for ( int k = 1 ; k <= n ; k ++ ) 
		{
			if ( !dq.empty() && dq.front() + m <= k ) dq.pop_front(); 
			while ( !dq.empty() && f1[i][j][k][l] <= f1[i][j][dq.back()][l]) dq.pop_back(); 
			dq.pb(k); 
			if ( k >= m ) f2 [i][j][k][l] = f1 [i][j][dq.front()][l] ; 
		}
	}
	
	for ( int i = 1 ; i <= n ; i ++ ) for ( int k = m ; k <= n ; k ++ ) for ( int l = m ; l <= n ; l ++ )
	{
		dq.clear() ; 
		for ( int j = 1 ; j <= n ; j ++ ) 
		{
			if ( !dq.empty() && dq.front() + m <= j ) dq.pop_front(); 
			while ( !dq.empty() && f2[i][j][k][l] <= f2[i][dq.back()][k][l]) dq.pop_back(); 
			dq.pb(j); 
			if ( j >= m ) f3 [i][j][k][l] = f2 [i][dq.front()][k][l] ; 
		}
	}
	
	for ( int j = m ; j <= n ; j ++ ) for ( int k = m ; k <= n ; k ++ ) for ( int l = m ; l <= n ; l ++ )
	{
		dq.clear() ; 
		for ( int i = 1 ; i <= n ; i ++ ) 
		{
			if ( !dq.empty() && dq.front() + m <= i ) dq.pop_front(); 
			while ( !dq.empty() && f3[i][j][k][l] <= f3[dq.back()][j][k][l]) dq.pop_back(); 
			dq.pb(i); 
			if ( i >= m ) f4 [i][j][k][l] = f3[dq.front()][j][k][l] ; 
		}
	}
	for ( int i = m ; i <= n ; i ++ ) for ( int j = m ; j <= n ; j ++ ) for ( int k = m ; k <= n ; k ++ ) for ( int l = m ; l <= n ; l ++ ) cout << f4 [i][j][k][l] << " " ; 

}

Compilation message

hyper.cpp: In function 'void rf()':
hyper.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 22876 KB Output is correct
5 Correct 5 ms 23052 KB Output is correct
6 Correct 11 ms 29276 KB Output is correct
7 Correct 9 ms 26972 KB Output is correct
8 Correct 20 ms 33116 KB Output is correct
9 Correct 30 ms 38928 KB Output is correct
10 Correct 21 ms 35160 KB Output is correct
11 Correct 54 ms 39924 KB Output is correct
12 Correct 103 ms 48580 KB Output is correct
13 Correct 80 ms 41300 KB Output is correct
14 Correct 137 ms 55380 KB Output is correct
15 Correct 206 ms 61192 KB Output is correct
16 Correct 118 ms 43344 KB Output is correct
17 Correct 139 ms 48980 KB Output is correct
18 Correct 258 ms 62896 KB Output is correct
19 Correct 180 ms 65108 KB Output is correct
20 Correct 149 ms 56660 KB Output is correct