Submission #38668

#	Time	Username	Problem	Language	Result	Execution time	Memory
38668		alenam0161	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	583 ms	38628 KiB

hyper

#include <bits/stdc++.h>

using namespace std;
const int N  = 37;

struct sptable{
    deque<pair<int,int>> q;
    void clear(){
        q.clear();
    }
    void push(int x){
        int qan = 1;
        while(!q.empty()&&q.back().first>x){
            qan+=q.back().second;q.pop_back();
        }
        q.push_back({x,qan});
    }
    void remove(){
        q.front().second--;
        while(!q.empty()&&q.front().second==0)q.pop_front();
    }
    int m(){
        if(q.empty())return 0;
        return q.front().first;
    }
}cur;

int a[N][N][N][N];
int dp1[N][N][N][N];
int dp2[N][N][N][N];
int dp3[N][N][N][N];
int dp4[N][N][N][N];
int main(){

    int n,m;
    scanf("%d%d",&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)
                    scanf("%d",&a[i][j][k][l]);
    //  i
    for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)
            for(int l=1;l<=n;++l){
                cur.clear();
                for(int i=1;i<m;++i){
                    cur.push(a[i][j][k][l]);
                }
                for(int i=m;i<=n;++i){
                    cur.push(a[i][j][k][l]);
                    dp1[i-m+1][j][k][l]=cur.m();
                    cur.remove();
                }
            }
    // j
    for(int i=1;i<=n-m+1;i++)
        for(int k=1;k<=n;++k)
            for(int l=1;l<=n;++l){
                cur.clear();
                for(int j=1;j<m;++j){
                    cur.push(dp1[i][j][k][l]);
                }
                for(int j=m;j<=n;++j){
                    cur.push(dp1[i][j][k][l]);
                    dp2[i][j-m+1][k][l]=cur.m();
                    cur.remove();
                }
            }
    // k
    for(int i=1;i<=n-m+1;++i)
        for(int j=1;j<=n-m+1;++j)
            for(int l=1;l<=n;++l){
                cur.clear();
                for(int k=1;k<m;++k){
                    cur.push(dp2[i][j][k][l]);
                }
                for(int k=m;k<=n;++k){
                    cur.push(dp2[i][j][k][l]);
                    dp3[i][j][k-m+1][l]=cur.m();
                    cur.remove();
                }
            }
    // l
    for(int i=1;i<=n-m+1;++i)
        for(int j=1;j<=n-m+1;++j)
            for(int k=1;k<=n-m+1;++k){
                cur.clear();
                for(int l=1;l<m;++l){
                    cur.push(dp3[i][j][k][l]);
                }
                for(int l=m;l<=n;++l){
                    cur.push(dp3[i][j][k][l]);
                    dp4[i][j][k][l-m+1]=cur.m();
                    cur.remove();
                }
            }
    for(int i=1;i<=n-m+1;++i)
        for(int j=1;j<=n-m+1;++j)
            for(int k=1;k<=n-m+1;++k)
                for(int l=1;l<=n-m+1;++l){
                    printf("%d ",dp4[i][j][k][l]);
                }
    return 0;
}

Compilation message (stderr)

hyper.cpp: In function 'int main()':
hyper.cpp:36:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
hyper.cpp:41:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                     scanf("%d",&a[i][j][k][l]);
                                               ^

• Subtask 1: 100 / 100