Submission #593796

#	Time	Username	Problem	Language	Result	Execution time	Memory
593796		oleh1421	Sandcastle 2 (JOI22_ho_t5)	C++17	9 / 100	6 ms	1288 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;
    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]) return false;
                }
            }
        }
    }

    return (cnt==((x2-x1+1)*(y2-y1+1)-1));
}
void solve(){
    int n,m;cin>>n>>m;

    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++){


                for (int y2=y1;y2<m;y2++){
                    if (ok(x1,y1,x2,y2)) {
                        res++;
                        cout<<y1<<" "<<y2<<endl;
                    }
                }
            }
        }
    }
    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:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int i=0;i<v.size();i++){
      |                      ~^~~~~~~~~

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