oj.uz

Submission #638742

# Submission time Handle Problem Language Result Execution time Memory
638742 2022-09-07T08:53:59 Z jamezzz Sandcastle 2 (JOI22_ho_t5) C++17
10 / 100
 5000 ms 9144 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2588 KB Output is correct
2 Execution timed out 5089 ms 9144 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Execution timed out 5075 ms 2916 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Execution timed out 5075 ms 2916 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Execution timed out 5075 ms 2916 KB Time limit exceeded
8 Halted 0 ms 0 KB -