| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 523419 |
2022-02-07T15:44:42 Z |
boykut |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
77728 KB |
#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
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;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
308 KB |
Output is correct |
| 3 |
Correct |
2 ms |
328 KB |
Output is correct |
| 4 |
Correct |
48 ms |
672 KB |
Output is correct |
| 5 |
Correct |
387 ms |
3012 KB |
Output is correct |
| 6 |
Correct |
525 ms |
20632 KB |
Output is correct |
| 7 |
Correct |
759 ms |
48212 KB |
Output is correct |
| 8 |
Correct |
686 ms |
44872 KB |
Output is correct |
| 9 |
Execution timed out |
2054 ms |
32384 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2055 ms |
34676 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2086 ms |
28160 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2058 ms |
34628 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2011 ms |
38180 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2052 ms |
28272 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2081 ms |
35716 KB |
Time limit exceeded |
| 16 |
Correct |
818 ms |
39404 KB |
Output is correct |
| 17 |
Execution timed out |
2009 ms |
41848 KB |
Time limit exceeded |
| 18 |
Correct |
718 ms |
44860 KB |
Output is correct |
| 19 |
Execution timed out |
2068 ms |
41560 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2061 ms |
77728 KB |
Time limit exceeded |
