oj.uz

Submission #251093

# Submission time Handle Problem Language Result Execution time Memory
251093 2020-07-20T07:16:54 Z dvdg6566 Strah (COCI18_strah) C++14
110 / 110
 457 ms 161784 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3200 KB Output is correct
2 Correct 2 ms 3200 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3200 KB Output is correct
2 Correct 3 ms 3200 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7808 KB Output is correct
2 Correct 11 ms 7680 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7936 KB Output is correct
2 Correct 11 ms 7680 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3200 KB Output is correct
2 Correct 12 ms 7680 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 47224 KB Output is correct
2 Correct 241 ms 101368 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 102520 KB Output is correct
2 Correct 394 ms 148856 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 60024 KB Output is correct
2 Correct 272 ms 110200 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20728 KB Output is correct
2 Correct 286 ms 104916 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 86264 KB Output is correct
2 Correct 457 ms 161784 KB Output is correct