제출 #779227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779227		vjudge1	Strah (COCI18_strah)	C++17	0 / 110	275 ms	165320 KiB

strah

#include <bits/stdc++.h>

using namespace std;

typedef long long lo; 

#define fi first
#define se second
#define int long long
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000;
const lo li = 2005;
const lo mod = 1000000007;

int n,m,a[li],k,flag,t,l[li][li],r[li][li],tree[li*4],lazy[li*4],tree2[li*4],lazy2[li*4],ans[li][li],dp[li][li],kac[li][li];
int cev;
string s[li];
vector<int> v;

inline void push(int node,int start,int end){
	if(lazy[node]==-1)return ;
	tree[node]=(end-start+1)*lazy[node];
	if(start!=end){
		lazy[node*2]=lazy[node];
		lazy[node*2+1]=lazy[node];
	}
	lazy[node]=-1;
}

inline void update(int node,int start,int end,int l,int r,int val){
	push(node,start,end);
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){lazy[node]=val;push(node,start,end);return ;}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=tree[node*2]+tree[node*2+1];
}

inline int query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	push(node,start,end);
	if(start>=l && end<=r)return tree[node];
	return query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r);
}

inline void push2(int node,int start,int end){
	if(lazy2[node]==-1)return ;
	tree2[node]=(end-start+1)*lazy2[node];
	if(start!=end){
		lazy2[node*2]=lazy2[node];
		lazy2[node*2+1]=lazy2[node];
	}
	lazy2[node]=-1;
}

inline void update2(int node,int start,int end,int l,int r,int val){
	push2(node,start,end);
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){lazy2[node]=val;push2(node,start,end);return ;}
	update2(node*2,start,mid,l,r,val),update2(node*2+1,mid+1,end,l,r,val);
	tree2[node]=tree2[node*2]+tree2[node*2+1];
}

inline int query2(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	push2(node,start,end);
	if(start>=l && end<=r)return tree2[node];
	return query2(node*2,start,mid,l,r)+query2(node*2+1,mid+1,end,l,r);
}

inline int in(){
	int x;
	cin>>x;
	return x;
}

int32_t main(void){
	//~ fio();
	n=in(),m=in();
	memset(lazy,-1,sizeof(lazy));
	memset(lazy2,-1,sizeof(lazy2));
	FOR{
		cin>>s[i];
		s[i]='0'+s[i];
		int ind=1;
		for(int j=1;j<=m;j++){
			if(s[i][j]=='#')ind=j+1;
			else l[i][j]=ind;
		}
		ind=m;
		for(int j=m;j>=1;j--){
			if(s[i][j]=='#')ind=j-1;
			else r[i][j]=ind;
		}
	}
	for(int i=1;i<=max(m,n)+1;i++){
		for(int j=1;j<=max(m,n)+1;j++){
			dp[i][j]=dp[i-1][j]+dp[i][j-1]+i*j-dp[i-1][j-1];
		}
	}
	for(int j=1;j<=m;j++){
		stack<pair<int,int>> st,st2;
		for(int i=1;i<=n;i++){
			if(s[i][j]=='#'){
				//burda her seyi sifirlayacagiz muhtemelen
				update(1,1,i,1,i,0);
				update2(1,1,i,1,i,0);
				st.push({j+1,i});
				//~ ans[i][j]=0;
				continue;
			}
			while(st.size() && st.top().fi<=l[i][j])st.pop();
			int lind=0;
			if(st.size())lind=st.top().se;
			int at=0;
			at+=dp[i-lind][j-l[i][j]+1];
			//~ cout<<at<<" ()() "<<i<<" ()() "<<j<<" ()() "<<lind<<endl;
			//~ if(st.size())at+=kac[lind][j]*((i-lind)*(j-st.top().fi+1));
			//~ cout<<at<<" AA "<<i<<" AA "<<j<<" AA "<<kac[lind][j]<<endl;
			ans[i][j]=(ans[lind][j]*(ans[lind][j]+1)/2)+at;
			kac[i][j]=kac[lind][j]+(i-lind)*(j-l[i][j]+1);
			st.push({l[i][j],i});
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cev+=ans[i][j];
			//~ cout<<i<<" :: "<<j<<" :: "<<ans[i][j]<<" :: "<<s[i][j]<<endl; 
		}
	} 
	cout<<cev<<endl;
	return 0;
}
/*
3 4
..#.
#...
...#
 
 
 */

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11