Submission #638742

#	Time	Username	Problem	Language	Result	Execution time	Memory
638742		jamezzz	Sandcastle 2 (JOI22_ho_t5)	C++17	10 / 100	5089 ms	9144 KiB

Main

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

#define fi first
#define se second
#define sf scanf
#define pf printf
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
#define all(x) x.begin(), x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());

#define maxn 50005
#define INF 1023456789

int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

set<int> s;

int h,w;
vector<vector<int>> a;
set<int> adj[maxn];

int main(){
	sf("%d%d",&h,&w);
	a.resize(h);
	vector<int> v;
	for(int i=0;i<h;++i){
		a[i].resize(w);
		for(int j=0;j<w;++j){
			sf("%d",&a[i][j]);
			v.push_back(a[i][j]);
		}
	}
	disc(v);
	for(int i=0;i<h;++i){
		for(int j=0;j<w;++j){
			a[i][j]=lb(v,a[i][j]);
		}
	}
	for(int i=0;i<h;++i){
		for(int j=0;j<w;++j){
			for(int k=0;k<4;++k){
				int nx=i+dx[k],ny=j+dy[k];
				if(nx<0||nx>=h||ny<0||ny>=w)continue;
				adj[a[i][j]].insert(a[nx][ny]);
			}
		}
	}
	ll ans=0;
	for(int l=0;l<h;++l){
		for(int r=l;r<h;++r){
			for(int _w=0;_w<w;++_w){
				s.clear();
				for(int i=_w;i<w;++i){
					for(int j=l;j<=r;++j){
						s.insert(a[j][i]);
					}
					bool pos=true;
					for(auto it=s.begin();it!=s.end();++it){
						int x=*it;
						if(it!=s.begin()){
							if(adj[*it].find(*prev(it))==adj[*it].end())pos=false;
						}
						if(next(it)!=s.end()){
							if(adj[*it].find(*next(it))==adj[*it].end())pos=false;
						}
						if(!pos)break;
					}
					if(pos)++ans;
				}
			}
		}
	}
	pf("%lld\n",ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:64:11: warning: unused variable 'x' [-Wunused-variable]
   64 |       int x=*it;
      |           ^
Main.cpp:28:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  sf("%d%d",&h,&w);
      |    ^
Main.cpp:34:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |    sf("%d",&a[i][j]);
      |      ^

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