# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
824444 | PoonYaPat | Sandcastle 2 (JOI22_ho_t5) | C++14 | 2 ms | 340 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int h,w,c[5000][5000],val[50005];
ll ans,dp1[50005],dp2[50005];
map<int,int> mp;
int cc=0;
void dfs(int x, int y) {
++cc;
if (mp[c[x-1][y]]==cc+1) dfs(x-1,y);
else if (mp[c[x+1][y]]==cc+1) dfs(x+1,y);
else if (mp[c[x][y-1]]==cc+1) dfs(x,y-1);
else if (mp[c[x][y+1]]==cc+1) dfs(x,y+1);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen("test.txt","r",stdin);
cin>>h>>w;
if (h==1) {
for (int i=1; i<=w; ++i) cin>>val[i];
for (int i=1; i<=w; ++i) {
if (i && val[i]>val[i-1]) dp1[i]=dp1[i-1]+1;
else dp1[i]=1;
ans+=dp1[i];
}
for (int i=w; i>=1; --i) {
if (i!=w && val[i]>val[i+1]) dp2[i]=dp2[i+1]+1;
else dp2[i]=1;
ans+=dp2[i]-1;
}
cout<<ans;
} else {
for (int i=1; i<=h; ++i) for (int j=1; j<=w; ++j) cin>>c[i][j];
for (int x1=1; x1<=h; ++x1) {
for (int y1=1; y1<=w; ++y1) {
for (int x2=x1; x2<=h; ++x2) {
for (int y2=y1; y2<=w; ++y2) {
mp.clear();
cc=0;
int mi=INT_MAX,X,Y;
for (int x=x1; x<=x2; ++x) {
for (int y=y1; y<=y2; ++y) {
mp[c[x][y]]=0;
if (c[x][y]<mi) {
mi=c[x][y];
X=x;
Y=y;
}
}
}
int cnt=0;
for (auto s : mp) mp[s.first]=++cnt;
dfs(X,Y);
if (cc==(x2-x1+1)*(y2-y1+1)) ++ans;
}
}
}
}
cout<<ans;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |