Submission #58118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58118	2018-07-16T21:30:49 Z	Benq	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	484 ms	43824 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[40][40][40][40];

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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	580 KB	Output is correct
3	Correct	6 ms	1068 KB	Output is correct
4	Correct	7 ms	1276 KB	Output is correct
5	Correct	8 ms	1300 KB	Output is correct
6	Correct	15 ms	2852 KB	Output is correct
7	Correct	13 ms	3176 KB	Output is correct
8	Correct	32 ms	5944 KB	Output is correct
9	Correct	74 ms	9028 KB	Output is correct
10	Correct	39 ms	9028 KB	Output is correct
11	Correct	106 ms	9492 KB	Output is correct
12	Correct	208 ms	11892 KB	Output is correct
13	Correct	176 ms	11892 KB	Output is correct
14	Correct	281 ms	16248 KB	Output is correct
15	Correct	427 ms	23104 KB	Output is correct
16	Correct	219 ms	23104 KB	Output is correct
17	Correct	329 ms	23104 KB	Output is correct
18	Correct	484 ms	25768 KB	Output is correct
19	Correct	373 ms	30448 KB	Output is correct
20	Correct	259 ms	43824 KB	Output is correct