| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 90693 |
2018-12-23T16:21:18 Z |
popovicirobert |
UFO (IZhO14_ufo) |
C++14 |
|
782 ms |
94464 KB |
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
struct SegTree {
vector <int> aint;
int n;
inline void init(int _n) {
n = _n;
aint.resize(4 * n + 1);
}
inline void refresh(int nod) {
aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
}
void update(int nod, int left, int right, int pos, int val) {
if(left == right) {
aint[nod] = val;
}
else {
int mid = (left + right) / 2;
if(pos <= mid) update(2 * nod, left, mid, pos, val);
else update(2 * nod + 1, mid + 1, right, pos, val);
refresh(nod);
}
}
int query_l(int nod, int left, int right, int l, int r, int val) {
if(l <= left && right <= r) {
int mid = (left + right) / 2;
if(aint[nod] < val) {
return -1;
}
if(left == right) {
return left;
}
if(aint[2 * nod] >= val) {
return query_l(2 * nod, left, mid, l, r, val);
}
return query_l(2 * nod + 1, mid + 1, right, l, r, val);
}
else {
int mid = (left + right) / 2;
int ans = -1;
if(l <= mid && aint[2 * nod] >= val) {
ans = query_l(2 * nod, left, mid, l, r, val);
}
if(mid < r && ans == -1 && aint[2 * nod + 1] >= val) {
ans = query_l(2 * nod + 1, mid + 1, right, l, r, val);
}
return ans;
}
}
int query_r(int nod, int left, int right, int l, int r, int val) {
if(l <= left && right <= r) {
int mid = (left + right) / 2;
if(aint[nod] < val) {
return -1;
}
if(left == right) {
return left;
}
if(aint[2 * nod + 1] >= val) {
return query_r(2 * nod + 1, mid + 1, right, l, r, val);
}
return query_r(2 * nod, left, mid, l, r, val);
}
else {
int mid = (left + right) / 2;
int ans = -1;
if(mid < r && aint[2 * nod + 1] >= val) {
ans = query_r(2 * nod + 1, mid + 1, right, l, r, val);
}
if(l <= mid && ans == -1 && aint[2 * nod] >= val) {
ans = query_r(2 * nod, left, mid, l, r, val);
}
return ans;
}
}
};
vector < vector <ll> > mat;
vector < SegTree > row, col;
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, j, n, m, r, k, p;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> r >> k >> p;
mat.resize(n + 1);
row.resize(n + 1), col.resize(m + 1);
for(i = 1; i <= n; i++) {
row[i].init(m);
}
for(i = 1; i <= m; i++) {
col[i].init(n);
}
mat[0].resize(m + 1);
for(i = 1; i <= n; i++) {
mat[i].resize(m + 1);
for(j = 1; j <= m; j++) {
cin >> mat[i][j];
row[i].update(1, 1, m, j, mat[i][j]);
col[j].update(1, 1, n, i, mat[i][j]);
}
}
while(k > 0) {
k--;
int id, h;
char ch;
cin >> ch >> id >> h;
if(ch == 'N') {
int pos = 0;
i = 0;
while(i < r && pos < n) {
pos = col[id].query_l(1, 1, n, pos + 1, n, h);
if(pos == -1) {
break;
}
mat[pos][id]--;
col[id].update(1, 1, n, pos, mat[pos][id]);
i++;
}
}
if(ch == 'S') {
int pos = n + 1;
i = 0;
while(i < r && pos > 1) {
pos = col[id].query_r(1, 1, n, 1, pos - 1, h);
if(pos == -1) {
break;
}
mat[pos][id]--;
col[id].update(1, 1, n, pos, mat[pos][id]);
i++;
}
}
if(ch == 'W') {
int pos = 0;
i = 0;
while(i < r && pos < m) {
pos = row[id].query_l(1, 1, m, pos + 1, m, h);
if(pos == -1) {
break;
}
mat[id][pos]--;
row[id].update(1, 1, m, pos, mat[id][pos]);
i++;
}
}
if(ch == 'E') {
int pos = m + 1;
i = 0;
while(i < r && pos > 1) {
pos = row[id].query_r(1, 1, m, 1, pos - 1, h);
if(pos == -1) {
break;
}
mat[id][pos]--;
row[id].update(1, 1, m, pos, mat[id][pos]);
i++;
}
}
}
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
}
}
ll ans = 0;
for(i = p; i <= n; i++) {
for(j = p; j <= m; j++) {
ans = max(ans, mat[i][j] - mat[i - p][j] - mat[i][j - p] + mat[i - p][j - p]);
}
}
cout << ans;
//cin.close();
//cout.close();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
568 KB |
Output is correct |
| 4 |
Correct |
11 ms |
820 KB |
Output is correct |
| 5 |
Correct |
54 ms |
2708 KB |
Output is correct |
| 6 |
Correct |
187 ms |
19816 KB |
Output is correct |
| 7 |
Correct |
282 ms |
45136 KB |
Output is correct |
| 8 |
Correct |
272 ms |
45136 KB |
Output is correct |
| 9 |
Correct |
439 ms |
45136 KB |
Output is correct |
| 10 |
Correct |
492 ms |
45136 KB |
Output is correct |
| 11 |
Correct |
379 ms |
45136 KB |
Output is correct |
| 12 |
Correct |
498 ms |
45184 KB |
Output is correct |
| 13 |
Correct |
624 ms |
48296 KB |
Output is correct |
| 14 |
Correct |
492 ms |
48296 KB |
Output is correct |
| 15 |
Correct |
528 ms |
48296 KB |
Output is correct |
| 16 |
Correct |
257 ms |
48296 KB |
Output is correct |
| 17 |
Correct |
761 ms |
48408 KB |
Output is correct |
| 18 |
Correct |
236 ms |
48408 KB |
Output is correct |
| 19 |
Correct |
347 ms |
50628 KB |
Output is correct |
| 20 |
Correct |
782 ms |
94464 KB |
Output is correct |
