Submission #523419

#	Time	Username	Problem	Language	Result	Execution time	Memory
523419		boykut	UFO (IZhO14_ufo)	C++14	50 / 100	2086 ms	77728 KiB

ufo

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> a;
vector<vector<long long>> pref;

struct segment_tree {
	int n;
	vector<int> t;
	segment_tree() {
	}
	segment_tree(size_t s) {
		n = 1;
		while (n < s) n <<= 1;
		t.assign(2 * n, 0);
	}
	void update(int i, int x, int v, int vl, int vr) {
		if (vl == vr) {
			t[v] += x;
		} else {
			int vm = vl + vr >> 1;
			if (i <= vm)
				update(i, x, v << 1, vl, vm);
			else
				update(i, x, v << 1 | 1, vm + 1, vr);
			t[v] = max(t[v << 1], t[v << 1 | 1]);
		}
	}
	void update(int i, int x) {
		update(i, x, 1, 0, n - 1);
	}
	int query(int l, int r, int v, int vl, int vr) {
		if (l > vr || vl > r) return INT_MIN;
		if (l <= vl && vr <= r) return t[v];
		int vm = vl + vr >> 1;
		int q1 = query(l, r, v << 1, vl, vm);
		int q2 = query(l, r, v << 1 | 1, vm + 1, vr);
		return max(q1, q2);
	}
	int query(int l, int r) {
		return query(l, r, 1, 0, n - 1);
	}
};

vector<segment_tree> row, col;

int getmaxRow(int x, int l, int r) {
	//int ans = INT_MIN;
	//for (int j = l; j <= r; j++) ans = max(ans, a[x][j]);
	return row[x].query(l, r);
};

int getmaxCol(int x, int l, int r) {
	// int ans = INT_MIN;
	// for (int j = l; j <= r; j++) ans = max(ans, a[j][x]);
	return col[x].query(l, r);
};

void updateRow(int x, int j) {
	//a[x][j]--;
	row[x].update(j, -1);
	col[j].update(x, -1);
}
void updateCol(int x, int j) {
	//a[j][x]--;
	col[x].update(j, -1);
	row[j].update(x, -1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, r, k, p;
	cin >> n >> m >> r >> k >> p;

	a = vector<vector<int>>(n, vector<int>(m));
	row = vector<segment_tree> (n);
	col = vector<segment_tree> (m);

	for (int i = 0; i < n; i++) {
		row[i] = segment_tree(m);
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			row[i].update(j, a[i][j]);
		}
	}
	for (int j = 0; j < m; j++) {
		col[j] = segment_tree(n);
		for (int i = 0; i < n; i++) {
			col[j].update(i, a[i][j]);
		}
	}

	while (k--) {
		char c; cin >> c;
		int x, y; cin >> x >> y;
		int cnt = r;
		x--;		

		if (c == 'W') {
			int start = 0;
			while (cnt > 0 && start < m) {
				int l = start, r = m - 1;
				while (l < r) {
					int m = (l + r) / 2;
					if (getmaxRow(x, start, m) >= y)
						r = m;
					else
						l = m + 1;
				}
				if (getmaxRow(x, start, r) >= y) {
					updateRow(x, r);
					cnt--;
					start = r + 1;
				} else break;
			}
		} else if (c == 'E') {
			int start = m - 1;
			while (cnt > 0 && start >= 0) {
				int l = 0, r = start;
				while (l < r) {
					int m = (l + r + 1) / 2;
					if (getmaxRow(x, m, start) >= y)
						l = m;
					else
						r = m - 1;
				}
				if (getmaxRow(x, l, start) >= y) {
					updateRow(x, l);
					cnt--;
					start = l - 1;
				} else break;
			}
		} else if (c == 'N') {
			int start = 0;
			while (cnt > 0 && start < n) {
				int l = start, r = n - 1;
				while (l < r) {
					int m = (l + r) / 2;
					if (getmaxCol(x, start, m) >= y)
						r = m;
					else
						l = m + 1;
				}
				if (getmaxCol(x, start, r) >= y) {
					updateCol(x, r);
					cnt--;
					start = r + 1;
				} else break;
			}
		} else {
			int start = n - 1;
			while (cnt > 0 && start >= 0) {
				int l = 0, r = start;
				while (l < r) {
					int m = (l + r + 1) / 2;
					if (getmaxCol(x, m, start) >= y)
						l = m;
					else
						r = m - 1;
				}
				if (getmaxCol(x, l, start) >= y) {
					updateCol(x, l);
					cnt--;
					start = l - 1;
				} else break;
			}
		}
	}

	//cout << row[0].query(0, m-1) << '\n';

	pref = vector<vector<long long>>(n, vector<long long>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			a[i][j] = row[i].query(j, j);
			//cout << a[i][j] << ' ';
			pref[i][j] = a[i][j];
			pref[i][j] += (i ? pref[i-1][j] : 0);
			pref[i][j] += (j ? pref[i][j-1] : 0);
			pref[i][j] -= (i && j ? pref[i-1][j-1] : 0);
		}
		cout << '\n';
	}

	auto get = [&](int a, int b, int c, int d) ->long long {
		long long s = pref[c][d];
		s -= (a ? pref[a-1][d] : 0);
		s -= (b ? pref[c][b-1] : 0);
		s += (a && b ? pref[a-1][b-1] : 0);
		return s;
	};

	long long ans = LLONG_MIN;
	for (int i = 0; i + p - 1 < n; i++) {
		for (int j = 0; j + p - 1 < m; j++) {
			ans = max(ans, get(i, j, i + p - 1, j + p - 1));
		}
	}
	cout << ans << '\n';

	return 0;
}

Compilation message (stderr)

ufo.cpp: In constructor 'segment_tree::segment_tree(size_t)':
ufo.cpp:15:12: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   while (n < s) n <<= 1;
      |          ~~^~~
ufo.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
ufo.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |    int vm = vl + vr >> 1;
      |             ~~~^~~~
ufo.cpp: In member function 'int segment_tree::query(int, int, int, int, int)':
ufo.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int vm = vl + vr >> 1;
      |            ~~~^~~~

• Subtask 1: 50 / 100