Submission #834103

#	Time	Username	Problem	Language	Result	Execution time	Memory
834103		vjudge1	Bomb (IZhO17_bomb)	C++17	0 / 100	91 ms	131072 KiB

bomb

#include<bits/stdc++.h>
using namespace std;

// // PBDS Template
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//
//template <class T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
//using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

// Preset
const int maxn = 10000;
const int INF = INT_MAX;
const long long int LINF = LLONG_MAX;
const long long int mod = 1e9 + 7;
const long long int mod2 = 998244353;
//const double e = 2.71828;
const double PI = acos(-1);
const double eps = 1e-10;
#define pb push_back
#define ll long long
#define ull unsigned long long
typedef pair<char,char> pc;
typedef pair<double,double> pd;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<pi,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<string,int> psi;
typedef pair<int,string> pis;
typedef pair<char,int> pci;
typedef pair<int,char> pic;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
int dr[4] = {0,1,0,-1}, dc[4] = {1,0,-1,0};

int t[2505][maxn+5], lazy[2505][maxn+5];

// build
void build(int i, vector<ll> &a, int v, int st, int en) {
	if (st == en) {
		t[i][v] = a[st];
		return;
	}
	int mid = (st + en) / 2;
	build(i, a, 2*v, st, mid);
	build(i, a, 2*v+1, mid + 1, en);
	if (t[i][2*v] == t[i][2*v+1]) t[i][v] = t[i][2*v];
}

// push lazy
void push (int i, int v) {
	if (lazy[i][v]) {
		t[i][v*2] = t[i][v*2+1] = t[i][v];
		lazy[i][v*2] = lazy[i][v*2+1] = 1;
		lazy[i][v] = 0;
	}
}

// update
void update(int i, int v, int st, int en, int l, int r, int val) {
	if (l>r) return;
	if (st==l && en==r) {
		t[i][v] = val;
		lazy[i][v] = 1;
	}
	else {
		push(i,v);
		int mid = (st+en)/2;
		update(i,v*2,st,mid,l,min(r,mid),val);
		update(i,v*2+1,mid+1,en,max(l,mid+1),r,val);
	}
}

// query
int query(int i, int v, int st, int en, int p) {
	if (st==en) return t[i][v];
	push(i,v);
	int mid = (st+en)/2;
	if (p<=mid) return query(i, v*2, st, mid, p);
	else return query(i, v*2+1, mid+1, en, p);
}


void solve() {
	ll n,m;
	cin >> n >> m;
	string s[n+5];
	for (ll i=0; i<n; i++) {
		cin >> s[i];
	}
	vector<vector<ll>> a(n+1, vector<ll>(m+1)), b(m+1, vector<ll>(n+1)), ps(n+1, vector<ll>(m+1,0));
	for (ll i=0; i<n; i++) {
		for (ll j=0; j<m; j++) {
			a[i+1][j+1] = (s[i][j]=='0') ? 0ll : 1ll;
		}
	}
	for (int i=0; i<m; i++) {
		for (int j=0; j<n; j++) {
			b[i+1][j+1] = (s[j][i]=='0') ? 0ll : 1ll;
		}
	}
	for (int i=1; i<=n; i++) ps[i][1] = ps[i-1][1] + a[i][1];
	for (int i=1; i<=m; i++) ps[1][i] = ps[1][i-1] + a[1][i];
	for (int i=2; i<=n; i++) {
		for (int j=2; j<=m; j++) {
			ps[i][j] = ps[i][j-1] + ps[i-1][j] - ps[i-1][j-1] + a[i][j];
		}
	}
	
	int h = 0, w = 0;
	
	// binser for height
	int l = 1, r = n;
	while (l<=r) {
		int mid = l + (r-l)/2;
		memset(lazy,0,sizeof(lazy));
		memset(t,-1,sizeof(t));
		for (int i=1; i<=m; i++) {
			build(i,b[i],1,1,n);
//			for (int j=1; j<=n; j++) cout << query(i,1,1,n,j) << ' ';
//			cout << endl;
		}
		for (int i=1; i<=m; i++) {
			for (int j=1; j<=n-mid+1; j++) {
				int area = ps[j+mid-1][i] - ps[j+mid-1][i-1] - ps[j-1][i] + ps[j-1][i-1];
				if (area == mid) {
					update(i,1,1,n,j,j+mid-1,0);
				}
			}
		}
		int sum = 0;
		for (int i=1; i<=m; i++) {
			for (int j=1; j<=n; j++) sum += query(i,1,1,n,j);
		}
		if (sum==0) {
			h = max(h, mid);
			l = mid+1;
		}
		else r = mid-1;
	}
	
	// binser for width
	l = 1, r = m;
	while (l<=r) {
		int mid = l + (r-l)/2;
		memset(lazy,0,sizeof(lazy));
		memset(t,-1,sizeof(t));
		for (int i=1; i<=n; i++) {
			build(i,a[i],1,1,m);
		}
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=m-mid+1; j++) {
				int area = ps[i][j+mid-1] - ps[i][j-1] - ps[i-1][j+mid-1] + ps[i-1][j-1];
				if (area == mid) {
					update(i,1,1,m,j,j+mid-1,0);
				}
			}
		}
		int sum = 0;
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=m; j++) sum += query(i,1,1,m,j);
		}
		if (sum==0) {
			w = max(w, mid);
			l = mid+1;
		}
		else r = mid-1;
	}
	
	int ans = h*w;
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	precompute();
//	FFT::init_fft();
	int tc=1;
//	cin >> tc;
//	getchar();
//	int idx = 0;
	while (tc--) solve();
 	return 0;
}

• Subtask 1: 0 / 100