oj.uz

Submission #313650

# Submission time Handle Problem Language Result Execution time Memory
313650 2020-10-16T13:53:02 Z PixelCat Strah (COCI18_strah) C++14
110 / 110
 164 ms 35836 KB 
/*        _____ __  __
  /^--^\  | () )\ \/ /
  \____/  |_()_) |__| 
 /      \ _____  _ __  __ ____  _     ____   ____  _____ 
|        || ()_)| |\ \/ /| ===|| |__ / (__` / () \|_   _|
 \__  __/ |_|   |_|/_/\_\|____||____|\____)/__/\__\ |_|  
|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|
| | |\ \| | | | | | | | | | | | | | | | | | | | | | | | |
#####/ /#################################################
| | |\/ | | | | | | | | | | | | | | | | | | | | | | | | |
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| |
#include <Orz/i_am_noob.h>
#include <Orz/balbit.h>
#include <Orz/nathanlee726.h>*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<ll,ll>;
#define int ll

#define For(i,a,b)  for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (ll)(1e9+7)
#define INF (1e18)
#define EPS (1e-6)

#ifdef LOCALMEOW
#define debug(...) do{\
	cerr << __PRETTY_FUNCTION__ << " - " << __LINE__ <<\
	" : ("#__VA_ARGS__ << ") = ";\
	_OUT(__VA_ARGS__);\
}while(0)
template<typename T> void _OUT(T x) { cerr << x << "\n"; }
template<typename T,typename...I>
void _OUT(T x,I ...tail) { cerr << x << ", "; _OUT(tail...); }
#else
#define debug(...)
#endif
void INIT(){ ios::sync_with_stdio(false); cin.tie(0); }

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p){
	int ans=1,now=b;
	while(p){
		if(p&1) ans=ans*now%MOD;
		p/=2; now=now*now%MOD;
	}
	return ans;
}

char g[2010][2010];
int h[2010][2010];

int32_t main(){
	INIT();
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//code...
	int n,m; cin>>n>>m;
	For(i,0,n-1) For(j,0,m-1) cin>>g[i][j];
	For(i,0,n-1) For(j,0,m-1){
		if(g[i][j]=='#') h[i][j]=0;
		else if(i==0) h[i][j]=1;
		else h[i][j]=h[i-1][j]+1;
	}
	//For(i,0,n-1) For(j,0,m-1) cout<<h[i][j]<<" \n"[j==m-1];
	//For(i,0,n-1) For(j,0,m-1) cout<<g[i][j]<<" \n"[j==m-1];
	stack<pii> st;
	int ans=0;
	For(i,0,n-1){
		while(!st.empty()) st.pop();
		st.emplace(0,-1);
		int now=0,add=0;
		//cerr<<st.top().F<<" "<<st.top().S<<"\n";
		For(j,0,m-1){
			while(st.top().F>h[i][j]){
				auto p=st.top(); st.pop();
				add-=(p.S-st.top().S)*p.F*(p.F+1)/2;
				now-=(j*2-p.S-st.top().S+1)*(p.S-st.top().S)/2*p.F*(p.F+1)/2;
			}
			now+=h[i][j]*(h[i][j]+1)/2*(j-st.top().S+1)*(j-st.top().S)/2;
			add+=h[i][j]*(h[i][j]+1)/2*(j-st.top().S);
			ans+=now;
			now+=add;
			st.emplace(h[i][j],j);
			//cerr<<i<<" "<<j<<" "<<now<<" "<<add<<" "<<st.top().F<<" "<<st.top().S<<"\n";
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13560 KB Output is correct
2 Correct 95 ms 27128 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 23940 KB Output is correct
2 Correct 156 ms 34680 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 15480 KB Output is correct
2 Correct 106 ms 28876 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13304 KB Output is correct
2 Correct 116 ms 33540 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 35704 KB Output is correct
2 Correct 164 ms 35836 KB Output is correct