Submission #1329478

#TimeUsernameProblemLanguageResultExecution timeMemory
1329478Faisal_SaqibHyper-minimum (IZhO11_hyper)C++20
100 / 100
286 ms48728 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    int a[n][n][n][n];
    int og[n][n][n][n];
    int b[n][n][n][n];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int p=0;p<n;p++)
            {
                deque<int> q;
                for(int l=0;l<n;l++)
                {
                    cin>>a[i][j][p][l];
                    og[i][j][p][l]=a[i][j][p][l];
                    // cout<<a[i][j][p][l]<<' ';
                    while(q.size()>0 and a[i][j][p][q.back()]>=a[i][j][p][l])q.pop_back();
                    while(q.size()>0 and l-q.front()>=m)q.pop_front();
                    q.push_back(l);
                    if(l>=m-1)b[i][j][p][l-(m-1)]=a[i][j][p][q.front()];
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int p=0;p<n-m+1;p++)
            {
                deque<int> q;
                for(int l=0;l<n;l++)
                {
                    a[i][j][l][p]=b[i][j][l][p];
                    // cout<<a[i][j][p][l]<<' ';
                    while(q.size()>0 and a[i][j][q.back()][p]>=a[i][j][l][p])q.pop_back();
                    while(q.size()>0 and l-q.front()>=m)q.pop_front();
                    q.push_back(l);
                    if(l>=m-1)b[i][j][l-(m-1)][p]=a[i][j][q.front()][p];
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n-m+1;j++)
        {
            for(int p=0;p<n-m+1;p++)
            {
                deque<int> q;
                for(int l=0;l<n;l++)
                {
                    a[i][l][j][p]=b[i][l][j][p];
                    // cout<<a[i][j][p][l]<<' ';
                    while(q.size()>0 and a[i][q.back()][j][p]>=a[i][l][j][p])q.pop_back();
                    while(q.size()>0 and l-q.front()>=m)q.pop_front();
                    q.push_back(l);
                    if(l>=m-1)b[i][l-(m-1)][j][p]=a[i][q.front()][j][p];
                }
            }
        }
    }
    for(int i=0;i<n-m+1;i++)
    {
        for(int j=0;j<n-m+1;j++)
        {
            for(int p=0;p<n-m+1;p++)
            {
                deque<int> q;
                for(int l=0;l<n;l++)
                {
                    a[l][i][j][p]=b[l][i][j][p];
                    // cout<<a[i][j][p][l]<<' ';
                    while(q.size()>0 and a[q.back()][i][j][p]>=a[l][i][j][p])q.pop_back();
                    while(q.size()>0 and l-q.front()>=m)q.pop_front();
                    q.push_back(l);
                    if(l>=m-1)b[l-(m-1)][i][j][p]=a[q.front()][i][j][p];
                }
            }
        }
    }
    for(int i=0;i<n-m+1;i++)
    {
        for(int j=0;j<n-m+1;j++)
        {
            for(int p=0;p<n-m+1;p++)
            {
                for(int l=0;l<n-m+1;l++)
                {
                    cout<<b[i][j][p][l]<<' ';
                }
            }
        }
    }
    cout<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...