답안 #58117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58117	2018-07-16T21:29:48 Z	Benq	최솟값 배열 (IZhO11_hyper)	C++14	0 / 100	514 ms	92636 KB

hyper

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N,M, X[34][34][34][34];

void solve(int d) {
    if (d == 3) {
        F0R(i,N) F0R(j,N) F0R(k,N) {
            deque<pi> d;
            F0Rd(l,N) {
                while (sz(d) && d.back().f >= X[i][j][k][l]) d.pop_back();
                d.pb({X[i][j][k][l],l});
                if (l <= N-M) {
                    while (d.front().s >= l+M) d.pop_front();
                    X[i][j][k][l] = d.front().f;
                }
            }
        }
    } else if (d == 2) {
        F0R(i,N) F0R(j,N) F0R(l,N-M+1) {
            deque<pi> d;
            F0Rd(k,N) {
                while (sz(d) && d.back().f >= X[i][j][k][l]) d.pop_back();
                d.pb({X[i][j][k][l],k});
                if (k <= N-M) {
                    while (d.front().s >= k+M) d.pop_front();
                    X[i][j][k][l] = d.front().f;
                }
            }
        }
    } else if (d == 1) {
    	F0R(i,N) F0R(k,N-M+1) F0R(l,N-M+1) {
            deque<pi> d;
            F0Rd(j,N) {
                while (sz(d) && d.back().f >= X[i][j][k][l]) d.pop_back();
                d.pb({X[i][j][k][l],j});
                if (j <= N-M) {
                    while (d.front().s >= j+M) d.pop_front();
                    X[i][j][k][l] = d.front().f;
                }
            }
        }
    } else {
    	F0R(j,N-M+1) F0R(k,N-M+1) F0R(l,N-M+1) {
            deque<pi> d;
            F0Rd(i,N) {
                while (sz(d) && d.back().f >= X[i][j][k][l]) d.pop_back();
                d.pb({X[i][j][k][l],i});
                if (i <= N-M) {
                    while (d.front().s >= i+M) d.pop_front();
                    X[i][j][k][l] = d.front().f;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    F0R(i,N) F0R(j,N) F0R(k,N) F0R(l,N) cin >> X[i][j][k][l];
    F0Rd(i,4) solve(i);
    F0R(i,N-M+1) F0R(j,N-M+1) F0R(k,N-M+1) F0R(l,N-M+1) cout << X[i][j][k][l] << " ";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	748 KB	Output is correct
3	Correct	7 ms	1392 KB	Output is correct
4	Correct	7 ms	1500 KB	Output is correct
5	Correct	9 ms	1608 KB	Output is correct
6	Correct	20 ms	2796 KB	Output is correct
7	Correct	17 ms	3184 KB	Output is correct
8	Correct	39 ms	5564 KB	Output is correct
9	Correct	58 ms	8916 KB	Output is correct
10	Correct	41 ms	8916 KB	Output is correct
11	Correct	104 ms	14740 KB	Output is correct
12	Correct	259 ms	24840 KB	Output is correct
13	Correct	168 ms	31920 KB	Output is correct
14	Correct	297 ms	45792 KB	Output is correct
15	Correct	514 ms	64432 KB	Output is correct
16	Correct	208 ms	65260 KB	Output is correct
17	Correct	252 ms	78800 KB	Output is correct
18	Incorrect	223 ms	92636 KB	Output isn't correct
19	Halted	0 ms	0 KB	-