Submission #740718

---

Source Code Expand

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,s,n) for(int (i)=(s);(i)<(s)+(n);(i)++)
#define inf 1000000007
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <math.h>
#include<algorithm>
using namespace std;
typedef pair<int,int> Pii;

int a[1000*1000];
int t[1000*1000];
bool check[1000*1000];

int main(){
	int H,W;
	long long int ans=0;
	vector<Pii> vec;
	cin>>H>>W;
	rep(i,H*W){
		cin>>a[i];
		t[i]=1;
		vec.push_back(Pii(a[i],i));
	}
	sort(vec.begin(),vec.end());
	rep(k,H*W){
		int i=vec[k].second/W,j=vec[k].second%W;
		if(i>0){
			if(a[(i-1)*W+j]>a[i*W+j]){
				t[(i-1)*W+j]+=t[i*W+j];
				t[(i-1)*W+j]%=inf;
			}
		}
		if(i<H-1){
			if(a[(i+1)*W+j]>a[i*W+j]){
				t[(i+1)*W+j]+=t[i*W+j];
				t[(i+1)*W+j]%=inf;
			}
		}
		if(j>0){
			if(a[i*W+j-1]>a[i*W+j]){
				t[i*W+j-1]+=t[i*W+j];
				t[i*W+j-1]%=inf;
			}
		}
		if(j<W-1){
			if(a[i*W+j+1]>a[i*W+j]){
				t[i*W+j+1]+=t[i*W+j];
				t[i*W+j+1]%=inf;
			}
		}
	}
	rep(i,H*W){
		ans+=t[i];
		ans%=inf;
	}
	cout<<ans<<endl;
	return 0;

	//37
}

Submission Info

Judge Result