Submission #833879

#	Time	Username	Problem	Language	Result	Execution time	Memory
833879		vjudge1	Bomb (IZhO17_bomb)	C++17	0 / 100	1048 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[maxn+5][maxn+5], lazy[maxn+5][maxn+5];

// build
void build(int i, vector<int> &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);
	t[i][v] = t[i][2*v] + t[i][2*v+1];
}

// update
void update(int i, int v, int st, int en, int l, int r, int val) {
	if (lazy[v] != 0) {
		t[i][v] = (en - st + 1) * lazy[i][v];
		
		if (st != en) {
			lazy[i][2*v] = lazy[i][v];
			lazy[i][2*v+1] = lazy[i][v];
		}
		lazy[i][v] = 0;
	}

  	if ((en < l) || (st > r)) {
   	 	return;
  	}

	if (st >= l && en <= r) {
	    t[i][v] = (en - st + 1) * val;
	    if (st != en) {
	      lazy[i][2*v] = val; 
	      lazy[i][2*v+1] = val;
	    }
	    return;
	}

	int mid = (st + en) / 2;
	update(i,2*v, st, mid, l, r, val);
	update(i,2*v+1, mid + 1, en, l, r, val);
	t[i][v] = (t[i][2*v] + t[i][2*v+1]);
}

// query
int query(int i, int v, int st, int en, int l, int r) {
	if (lazy[v] != 0) {
		t[i][v] = (en - st + 1) * lazy[i][v];
		if (st != en) {
	 		lazy[i][2*v] = lazy[i][v];
	  		lazy[i][2*v+1] = lazy[i][v];
		}
		lazy[i][v] = 0;
	}
	
	if (en < l || st > r) {
		return 0;
	}
	
	if ((l <= st) && (en <= r)) {
		return t[i][v];
	}
	
	int mid = (st + en) / 2;
	ll q1 = query(i, 2*v, st, mid, l, r);
	ll q2 = query(i, 2*v+1, mid + 1, en, l, r);
	return (q1 + q2);
}


void solve() {
	int n,m;
	cin >> n >> m;
	string s[n+5];
	for (int i=0; i<n; i++) {
		cin >> s[i];
	}
	vector<vector<int>> a(n+1, vector<int>(m+1)), b(m+1, vector<int>(n+1)), ps(n+1, vector<int>(m+1,0));
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			a[i+1][j+1] = (int)(s[i][j] - '0');
		}
	}
	for (int i=0; i<m; i++) {
		for (int j=0; j<n; j++) {
			b[i+1][j+1] = (int)(s[j][i] - '0');
		}
	}
	for (int i=1; i<=n; i++) ps[i][1] = a[i][1];
	for (int i=1; i<=m; i++) ps[1][i] = 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;
		for (int i=1; i<=m; i++) {
			build(i,b[i],1,1,n);
		}
		for (int i=1; i<=m; i++) {
			for (int j=1; j<=n-mid; j++) {
				int area = ps[j+mid][i] - ps[j-1][i];
				if (area == mid) {
					update(i,1,1,n,j,j+mid,0);
				}
			}
		}
		int sum = 0;
		for (int i=1; i<=m; i++) sum += query(i,1,1,n,1,n);
		cout << "height = " << mid << ' ' << sum << endl;
		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;
		for (int i=1; i<=n; i++) {
			build(i,a[i],1,1,m);
			for (int j=1; j<=m; j++) cout << query(i,1,1,m,j,j) << ' ';
			cout << endl;
		}
		cout << endl;
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=m-mid; j++) {
				int area = ps[i][j+mid] - ps[i][j-1];
				if (area == mid) {
					update(i,1,1,m,j,j+mid,0);
				}
			}
		}
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=m; j++) cout << query(i,1,1,m,j,j) << ' ';
			cout << endl;
		}
		int sum = 0;
		for (int i=1; i<=m; i++) sum += query(i,1,1,m,1,m);
		cout << "width = " << mid << ' ' << sum << endl;
		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