oj.uz

Submission #38668

# Submission time Handle Problem Language Result Execution time Memory
38668 2018-01-05T19:08:29 Z alenam0161 Hyper-minimum (IZhO11_hyper) C++14
100 / 100
 583 ms 38628 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 38628 KB Output is correct
2 Correct 0 ms 38628 KB Output is correct
3 Correct 3 ms 38628 KB Output is correct
4 Correct 0 ms 38628 KB Output is correct
5 Correct 6 ms 38628 KB Output is correct
6 Correct 16 ms 38628 KB Output is correct
7 Correct 13 ms 38628 KB Output is correct
8 Correct 39 ms 38628 KB Output is correct
9 Correct 66 ms 38628 KB Output is correct
10 Correct 39 ms 38628 KB Output is correct
11 Correct 133 ms 38628 KB Output is correct
12 Correct 269 ms 38628 KB Output is correct
13 Correct 186 ms 38628 KB Output is correct
14 Correct 296 ms 38628 KB Output is correct
15 Correct 459 ms 38628 KB Output is correct
16 Correct 326 ms 38628 KB Output is correct
17 Correct 339 ms 38628 KB Output is correct
18 Correct 583 ms 38628 KB Output is correct
19 Correct 469 ms 38628 KB Output is correct
20 Correct 363 ms 38628 KB Output is correct