Submission #593807

#	Time	Username	Problem	Language	Result	Execution time	Memory
593807		oleh1421	Sandcastle 2 (JOI22_ho_t5)	C++17	24 / 100	5048 ms	912 KiB

Main

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define y2 y_2
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
const ll inf=1e18;
mt19937 rnd(time(NULL));
const ll mod=998244353;
const int N=510;
const int Lg=16;
vector<vector<int> >a;
bool ok(int x1,int y1,int x2,int y2){
    int cnt=0;
    int cnt1=0;
    for (int i=x1;i<=x2;i++){
        for (int j=y1;j<=y2;j++){
            int x=-1,y=-1;
            for (int dx=-1;dx<=1;dx++){
                for (int dy=-1;dy<=1;dy++){
                    if (dx && dy) continue;
                    if (!dx && !dy) continue;
                    int nx=i+dx,ny=j+dy;
                    if (nx<x1 || nx>x2 || ny<y1 || ny>y2) continue;
                    if (a[nx][ny]<a[i][j]) continue;
                    if (x==-1 || a[x][y]>a[nx][ny]){
                        x=nx;
                        y=ny;
                    }
                }
            }
            if (x==-1) continue;
            cnt++;
            for (int dx=-1;dx<=1;dx++){
                for (int dy=-1;dy<=1;dy++){
                    if (dx && dy) continue;
                    if (!dx && !dy) continue;
                    int nx=x+dx,ny=y+dy;
                    if (nx<x1 || nx>x2 || ny<y1 || ny>y2) continue;
                    if (a[nx][ny]<a[x][y] && a[i][j]<a[nx][ny]) cnt1++;
                }
            }
        }
    }

    return (cnt==((x2-x1+1)*(y2-y1+1)-1) && cnt1==0);
}
void solve(){
    int n,m;cin>>n>>m;
    if (n>m){
        swap(n,m);
        a.resize(n);
        for (int i=0;i<n;i++){
            a[i].resize(m);
        }
        for (int j=0;j<m;j++){
            for (int i=0;i<n;i++){
                cin>>a[i][j];
            }
        }
    } else {
        a.resize(n);
        for (int i=0;i<n;i++){
            a[i].resize(m);
        }
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                cin>>a[i][j];
            }
        }
    }





    if (n==1){
        vector<int>v;
        for (int i=1;i<m;i++){
            v.push_back(a[0][i-1]<a[0][i]);
        }
        int res=m;
        int cnt=0;
        for (int i=0;i<v.size();i++){
            if (i>0 && v[i]==v[i-1]) cnt++;
            else cnt=1;
            res+=cnt;
        }
        cout<<res<<endl;
        return;

    }

    int res=0;
    for (int x1=0;x1<n;x1++){
        for (int y1=0;y1<m;y1++){
            for (int x2=x1;x2<n;x2++){
                int cnt=0;
                int cnt1=0;
                for (int y2=y1;y2<m;y2++){
                    for (int i=x1;i<=x2;i++){

                        for (int j=max(y1,y2-2);j<y2;j++){
                            {
                                int x=-1,y=-1;
                                for (int dx=-1;dx<=1;dx++){
                                    for (int dy=-1;dy<=1;dy++){
                                        if (dx && dy) continue;
                                        if (!dx && !dy) continue;
                                        int nx=i+dx,ny=j+dy;
                                        if (nx<x1 || nx>x2 || ny<y1 || ny>=y2) continue;
                                        if (a[nx][ny]<a[i][j]) continue;
                                        if (x==-1 || a[x][y]>a[nx][ny]){
                                            x=nx;
                                            y=ny;
                                        }
                                    }
                                }
                                if (x==-1) continue;
                                cnt--;
                                for (int dx=-1;dx<=1;dx++){
                                    for (int dy=-1;dy<=1;dy++){
                                        if (dx && dy) continue;
                                        if (!dx && !dy) continue;
                                        int nx=x+dx,ny=y+dy;
                                        if (nx<x1 || nx>x2 || ny<y1 || ny>=y2) continue;
                                        if (a[nx][ny]<a[x][y] && a[i][j]<a[nx][ny]) cnt1--;
                                    }
                                }

                            }

                        }
                    }
                    for (int i=x1;i<=x2;i++){
                        for (int j=max(y1,y2-2);j<=y2;j++){
                            {
                                int x=-1,y=-1;
                                for (int dx=-1;dx<=1;dx++){
                                    for (int dy=-1;dy<=1;dy++){
                                        if (dx && dy) continue;
                                        if (!dx && !dy) continue;
                                        int nx=i+dx,ny=j+dy;
                                        if (nx<x1 || nx>x2 || ny<y1 || ny>y2) continue;
                                        if (a[nx][ny]<a[i][j]) continue;
                                        if (x==-1 || a[x][y]>a[nx][ny]){
                                            x=nx;
                                            y=ny;
                                        }
                                    }
                                }
                                if (x==-1) continue;
                                cnt++;
                                for (int dx=-1;dx<=1;dx++){
                                    for (int dy=-1;dy<=1;dy++){
                                        if (dx && dy) continue;
                                        if (!dx && !dy) continue;
                                        int nx=x+dx,ny=y+dy;
                                        if (nx<x1 || nx>x2 || ny<y1 || ny>y2) continue;
                                        if (a[nx][ny]<a[x][y] && a[i][j]<a[nx][ny]) cnt1++;
                                    }
                                }

                            }

                        }
                    }
                    if (cnt==((x2-x1+1)*(y2-y1+1)-1) && cnt1==0) res++;
                }
            }
        }
    }
    cout<<res<<endl;
}
int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
//    cin>>tt;
    while (tt--){
        solve();
    }
    return 0;

}


/**
3
5 2 7 3 1 6 8 4
**/

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i=0;i<v.size();i++){
      |                      ~^~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 0 / 56
• Subtask 5: 0 / 20