| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171762 |
2019-12-30T10:38:51 Z |
VEGAnn |
UFO (IZhO14_ufo) |
C++14 |
|
1711 ms |
126336 KB |
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define MP3(a,b,c) MP(MP(a, b), c)
using namespace std;
const int oo = 1e9;
const int N = 1000100;
const int K = 110;
const int PW = 20;
vector<vector<int> > a, pref;
int n, m, R, k, p, pos;
bool fd;
int ans = 0;
struct seg_tree{
vector<int> mx;
int tp, nm;
seg_tree(): mx(0), tp(-1), nm(-1) {}
seg_tree(int _tp, int _nm): mx(0), tp(_tp), nm(_nm) {
if (tp == 0){
mx.resize(4 * m);
build(1, 0, m - 1);
} else {
mx.resize(4 * n);
build(1, 0, n - 1);
}
}
void build(int v, int l, int r){
if (l == r){
if (tp == 0)
mx[v] = a[nm][l];
else mx[v] = a[l][nm];
return;
}
int md = (l + r) >> 1;
build(v + v, l, md);
build(v + v + 1, md + 1, r);
mx[v] = max(mx[v + v], mx[v + v + 1]);
}
void real_search_rgt(int v, int l, int r, int vl){
if (l == r){
fd = 1;
pos = l;
return;
}
int md = (l + r) >> 1;
if (mx[v + v + 1] >= vl)
real_search_rgt(v + v + 1, md + 1, r, vl);
else real_search_rgt(v + v, l, md, vl);
}
void search_rgt(int v, int tl, int tr, int l, int r, int vl){
if (l > r || fd) return;
if (tl == l && tr == r){
if (mx[v] >= vl)
real_search_rgt(v, l, r, vl);
return;
}
int md = (tl + tr) >> 1;
search_rgt(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);
search_rgt(v + v, tl, md, l, min(r, md), vl);
}
void real_search_lft(int v, int l, int r, int vl){
if (l == r){
fd = 1;
pos = l;
return;
}
int md = (l + r) >> 1;
if (mx[v + v] >= vl)
real_search_lft(v + v, l, md, vl);
else real_search_lft(v + v + 1, md + 1, r, vl);
}
void search_lft(int v, int tl, int tr, int l, int r, int vl){
if (l > r || fd) return;
if (tl == l && tr == r){
if (mx[v] >= vl)
real_search_lft(v, l, r, vl);
return;
}
int md = (tl + tr) >> 1;
search_lft(v + v, tl, md, l, min(r, md), vl);
search_lft(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);
}
void update(int v, int l, int r, int ps){
if (l == r){
if (tp == 0)
mx[v] = a[nm][l];
else mx[v] = a[l][nm];
return;
}
int md = (l + r) >> 1;
if (ps <= md)
update(v + v, l, md, ps);
else update(v + v + 1, md + 1, r, ps);
mx[v] = max(mx[v + v], mx[v + v + 1]);
}
};
seg_tree row[N], col[N];
int main(){
cin >> n >> m >> R >> k >> p;
a.resize(n);
for (int i = 0; i < n; i++){
a[i].resize(m);
for (int j = 0; j < m; j++)
cin >> a[i][j];
}
for (int i = 0; i < n; i++)
row[i] = seg_tree(0, i);
for (int i = 0; i < m; i++)
col[i] = seg_tree(1, i);
for (; k; k--){
char tp; int nm, ht;
cin >> tp >> nm >> ht;
nm--;
if (tp == 'N'){
int pr = -1;
for (int it = 0; it < R; it++){
fd = 0;
pos = -1;
col[nm].search_lft(1, 0, n - 1, pr + 1, n - 1, ht);
if (!fd) break;
pr = pos;
a[pos][nm]--;
col[nm].update(1, 0, n - 1, pos);
row[pos].update(1, 0, m - 1, nm);
}
} else if (tp == 'S'){
int pr = n;
for (int it = 0; it < R; it++){
fd = 0;
pos = -1;
col[nm].search_rgt(1, 0, n - 1, 0, pr - 1, ht);
if (!fd) break;
pr = pos;
a[pos][nm]--;
col[nm].update(1, 0, n - 1, pos);
row[pos].update(1, 0, m - 1, nm);
}
} else if (tp == 'W'){
int pr = -1;
for (int it = 0; it < R; it++){
fd = 0;
pos = -1;
row[nm].search_lft(1, 0, m - 1, pr + 1, m - 1, ht);
if (!fd) break;
pr = pos;
a[nm][pos]--;
row[nm].update(1, 0, m - 1, pos);
col[pos].update(1, 0, n - 1, nm);
}
} else {
int pr = m;
for (int it = 0; it < R; it++){
fd = 0;
pos = -1;
row[nm].search_rgt(1, 0, m - 1, 0, pr - 1, ht);
if (!fd) break;
pr = pos;
a[nm][pos]--;
row[nm].update(1, 0, m - 1, pos);
col[pos].update(1, 0, n - 1, nm);
}
}
}
pref.resize(n + 1);
for (int i = 0; i <= n; i++)
pref[i].resize(m + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
pref[i][j] = a[i - 1][j - 1] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
for (int i = p; i <= n; i++)
for (int j = p; j <= m; j++){
int res = pref[i][j] - pref[i - p][j] - pref[i][j - p] + pref[i - p][j - p];
ans = max(ans, res);
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
62968 KB |
Output is correct |
| 2 |
Correct |
60 ms |
62968 KB |
Output is correct |
| 3 |
Correct |
63 ms |
63228 KB |
Output is correct |
| 4 |
Correct |
87 ms |
63484 KB |
Output is correct |
| 5 |
Correct |
233 ms |
65752 KB |
Output is correct |
| 6 |
Correct |
488 ms |
85624 KB |
Output is correct |
| 7 |
Correct |
855 ms |
112316 KB |
Output is correct |
| 8 |
Correct |
607 ms |
108664 KB |
Output is correct |
| 9 |
Correct |
830 ms |
106744 KB |
Output is correct |
| 10 |
Correct |
964 ms |
107880 KB |
Output is correct |
| 11 |
Correct |
768 ms |
106232 KB |
Output is correct |
| 12 |
Correct |
993 ms |
107640 KB |
Output is correct |
| 13 |
Correct |
1204 ms |
116080 KB |
Output is correct |
| 14 |
Correct |
912 ms |
106452 KB |
Output is correct |
| 15 |
Correct |
1088 ms |
109180 KB |
Output is correct |
| 16 |
Correct |
692 ms |
108524 KB |
Output is correct |
| 17 |
Correct |
1711 ms |
120608 KB |
Output is correct |
| 18 |
Correct |
684 ms |
113616 KB |
Output is correct |
| 19 |
Correct |
819 ms |
111208 KB |
Output is correct |
| 20 |
Correct |
1344 ms |
126336 KB |
Output is correct |
