제출 #251093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251093		dvdg6566	Strah (COCI18_strah)	C++14	110 / 110	457 ms	161784 KiB

strah

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=2100;
const ll MAXK=1000001;
const ll INF = 1e13;
const ll MOD = 1e9+7;

ll cost[MAXN];
ll R,C;
ll A[MAXN][MAXN];
queue<ll> ep[MAXN];
stack<ll> rm[MAXN];
ll cur,ans;

struct node{
	node *l,*r;
	int in;
	node(int i):in(i){
		l=r=nullptr;
	}
};
node* S[2010];

void del(ll x){
	++x;
	// cerr<<"Erasing "<<x<<'\n';

	int lft=S[x]->l->in;
	int rgt=S[x]->r->in;
	cur+=cost[rgt-lft-1];
	cur-=cost[rgt-x-1];
	cur-=cost[x-lft-1];
	S[x]->l->r = S[x]->r;
	S[x]->r->l = S[x]->l;
	S[x]=nullptr;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>R>>C;
	for(ll i=1;i<=C;++i){
		for(ll j=1;j<=i;++j){
			cost[i]+=j*(i-j+1);
		}
	}
	for(ll i=0;i<R;++i){
		string S;cin>>S;
		for(ll j=0;j<C;++j){
			if(S[j]=='#'){
				A[i][j]=1;
				ep[j].push(i);
			}
		}
	}

	// for(ll i=R-1;i>=0;--i){
	// 	for(ll j=0;j<C;++j)cerr<<A[i][j];
	// 	cerr<<'\n';
	// }

	for(ll lowp=0;lowp<R;++lowp){
		for(int i=0;i<=C+1;++i)S[i]=nullptr;
		cur=0;

		// cerr<<"Low row "<<lowp<<'\n';
		for(ll j=0;j<C;++j)if(SZ(ep[j])&&ep[j].front()<lowp){
			// cerr<<"Removing "<<j<<'\n';
			ep[j].pop();
		}
		vi tx;
		tx.pb(0);

		for(ll j=0;j<C;++j)if(SZ(ep[j])){
			rm[ep[j].front()].push(j);
			tx.pb(j+1);
		}
		tx.pb(C+1);
		for(auto i:tx)S[i]=new node(i);
		for(int i=0;i<SZ(tx)-1;++i){
			S[tx[i]]->r=S[tx[i+1]];
			cur+=cost[tx[i+1]-tx[i]-1];
		}
		for(int i=1;i<SZ(tx);++i){
			S[tx[i]]->l=S[tx[i-1]];
		}

		for(ll topr=R-1;topr>=lowp;--topr){
			// cerr<<"Bottom "<<lowp<<" top "<<topr<<" cost "<<cur*(topr-lowp+1)<<'\n';
			ans+=cur*(topr-lowp+1);
			while(SZ(rm[topr])){
				del(rm[topr].top());
				rm[topr].pop();
			}
		}
	}
	cout<<ans;
}

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