Submission #38818

#	Time	Username	Problem	Language	Result	Execution time	Memory
38818		Abelyan	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	683 ms	38624 KiB

hyper

#include <bits/stdc++.h>
using namespace std;


class min_queue{
public:
    void del(){
        while (ae>=0) {
            a.pop_back();
            ae--;
        }
        while(be>=0){
            b.pop_back();
            be--;
        }
    }
    void push(int k){
        if (ae!=-1) a.push_back(make_pair(k,min(k,a[ae].second)));
        else a.push_back(make_pair(k,k));
        ae++;
    }
    void pop(){
        if (be==-1){
            b.push_back(make_pair(a[ae].first,a[ae].first));
            ae--;
            a.pop_back();
            be++;
            while(ae>=0){
                b.push_back(make_pair(a[ae].first,min(a[ae].first,b[be].second)));
                a.pop_back();
                ae--;
                be++;
            }
        }
        b.pop_back();
        be--;
    }
    int mn(){
        int am=ae>=0?a[ae].second:INT_MAX;
        int bm=be>=0?b[be].second:INT_MAX;
        return min(am,bm);
    }
    min_queue(){
        ae=-1;
        be=-1;
    }
private:
    vector <pair<int,int > > a;
    vector <pair<int,int > > b;
    int ae,be;
};

const int N=37;

min_queue q;
int a[N][N][N][N];
int b1[N][N][N][N];
int b2[N][N][N][N];
int b3[N][N][N][N];
int b4[N][N][N][N];

int main()
{
    int n,m;
    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)
                    scanf("%d",&a[i][j][k][l]);
    for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)
            for(int l=1;l<=n;++l){
                q.del();
                for(int i=1;i<m;++i){
                    q.push(a[i][j][k][l]);
                }
                for(int i=m;i<=n;++i){
                    q.push(a[i][j][k][l]);
                    b1[i-m+1][j][k][l]=q.mn();
                    q.pop();
                }
            }
    for(int i=1;i<=n-m+1;i++)
        for(int k=1;k<=n;++k)
            for(int l=1;l<=n;++l){
                q.del();
                for(int j=1;j<m;++j){
                    q.push(b1[i][j][k][l]);
                }
                for(int j=m;j<=n;++j){
                    q.push(b1[i][j][k][l]);
                    b2[i][j-m+1][k][l]=q.mn();
                    q.pop();
                }
            }
    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){
                q.del();
                for(int k=1;k<m;++k){
                    q.push(b2[i][j][k][l]);
                }
                for(int k=m;k<=n;++k){
                    q.push(b2[i][j][k][l]);
                    b3[i][j][k-m+1][l]=q.mn();
                    q.pop();
                }
            }
    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){
                q.del();
                for(int l=1;l<m;++l){
                    q.push(b3[i][j][k][l]);
                }
                for(int l=m;l<=n;++l){
                    q.push(b3[i][j][k][l]);
                    b4[i][j][k][l-m+1]=q.mn();
                    q.pop();
                }
            }
    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 ",b4[i][j][k][l]);
                }
    return 0;
}

Compilation message (stderr)

hyper.cpp: In function 'int main()':
hyper.cpp:70: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