| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 338245 |
2020-12-22T20:00:28 Z |
Tosic |
UFO (IZhO14_ufo) |
C++14 |
|
451 ms |
262148 KB |
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int n, m, r, k, p;
vector<vector<int> > a, c, rv;
struct segtree
{
vector<int> tree;
vector<int> treeNum;
vector<int> a, resIdx;
int n, glR;
segtree(){
n=0;
glR = 0;
}
void init(int sz, vector<int> tmp){
n = sz;
tree.resize(4*n+10, 0);
treeNum.resize(4*n+10, 0);
a = tmp;
init(0, 0, n-1);
}
void kidsO(int idx){
tree[idx] = max(tree[idx*2+1], tree[idx*2+2]);
if(tree[idx*2+1] > tree[idx*2+2]){
treeNum[idx] = treeNum[idx*2+1];
} else if(tree[idx*2+2] > tree[2*idx+1]){
treeNum[idx] = treeNum[idx*2+2];
}else{
treeNum[idx] = treeNum[idx*2+1] + treeNum[idx*2+2];
}
}
void init(int idx, int l, int r){
if(l == r){
tree[idx] = a[l];
treeNum[idx] = 1;
return;
}
int mid = (l+r)/2;
init(idx*2+1, l ,mid);
init(idx*2+2, mid+1, r);
kidsO(idx);
}
void getF(int idx, int l, int r, int x){
// first index so a[l] >= x
if(tree[idx] < x){
return;
}
if(l == r){
--glR;//cerr << x << ' ' << tree[idx] << ' '<< l << '\n';
resIdx.push_back(l);
return;
}
int mid = (l+r)/2;
if(tree[1+2*idx] >= x){
getF(idx*2+1, l, mid, x);
}if(glR){
getF(idx*2+2, mid+1, r, x);
}
return;
return;
}
void getL(int idx, int l, int r, int x){
// lst index so a[l] >= x
if(tree[idx] < x){
return;
}
if(l == r){
//cerr << glR << '\n';
--glR;
resIdx.push_back(l);
return;
}
int mid = (l+r)/2;
if(tree[2+2*idx] >= x){
getL(idx*2+2, mid+1, r, x);
}
if(glR){
getL(2*idx+1, l, mid, x);
}
}
void upd(int idx, int l, int r, int x, int newV){
if(l == r){
a[l] += newV;
tree[idx] += newV;
return;
}
int mid = (l+r)/2;
if(x<=mid){
upd(2*idx+1, l, mid, x, newV);
}
if(x > mid){
upd(2*(idx+1), mid+1, r, x, newV);
}
kidsO(idx);
}
int query(int idx, int l, int r, int qL, int qR){
if(l > qR or r < qL){
return 0;
}
if(l >=qL and r <= qR){
return tree[idx];
}
int mid = (l+r)/2;
return max(query(idx*2+1, l, mid, qL, qR), query(idx*2+2, mid+1, r, qL, qR));
}
};
segtree rTrees[maxn], cTrees[maxn];
int tmpS(int x, int y){
if(x < 0 or y < 0){
return 0;
}
return c[x][y];
}
int getMax(){
for(int i = 0; i < m; ++i){
c[0][i] = a[0][i];
if(i){
c[0][i] += c[0][i-1];
}
}
for(int i = 0; i < n; ++i){
c[i][0] = a[i][0];
if(i){
c[i][0] += c[i-1][0];
}
}
for(int i = 1; i < n; ++i){
for(int j = 1; j < m; ++j){
c[i][j] = a[i][j]+c[i-1][j]+c[i][j-1]-c[i-1][j-1];
}
}
int res = 0;
for(int i = 0; i < n-p+1; ++i){
for(int j = 0; j < m-p+1; ++j){
res = max(tmpS(i+p-1, j+p-1) - tmpS(i+p-1, j-1) - tmpS(i-1, j+p-1) + tmpS(i-1, j-1), res);
}
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
cin >> n >> m >> r >> k >> p;
a.resize(n, vector<int>(m));
c.resize(n, vector<int>(m));
rv.resize(m, vector<int>(n));
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cin >> a[i][j];
}
rTrees[i].init(m, a[i]);
}
for(int i = 0; i < m; ++i){
for(int j = 0;j<n; ++ j){
rv[i][j] = a[j][i];
}
cTrees[i].init(n, rv[i]);
}
for(int i = 0; i < k; ++i){
char c;
int h, y;
cin >> c >> y >> h;
y--;
//for(int j = 0; j < r; ++j){
int tmp;
if(c == 'N'){
cTrees[y].resIdx.clear();
cTrees[y].glR = r;
cTrees[y].getF(0, 0, n-1, h);
for(auto tmp : cTrees[y].resIdx){
cTrees[y].upd(0, 0, n-1, tmp, -1);
rTrees[tmp].upd(0, 0, m-1, y, -1);
//cerr << tmp << ' ' << y << '\n';
a[tmp][y]--;
}
}
if(c == 'S'){
cTrees[y].resIdx.clear();
cTrees[y].glR =r;
cTrees[y].getL(0, 0, n-1, h);
for(auto tmp : cTrees[y].resIdx){
cTrees[y].upd(0, 0, n-1, tmp, -1);
rTrees[tmp].upd(0, 0, m-1, y, -1);
//cerr << tmp << ' ' << y<< '\n';
a[tmp][y]--;
}
}
if(c == 'W'){
rTrees[y].resIdx.clear();
rTrees[y].glR = r;
rTrees[y].getF(0, 0, m-1, h);
for(auto tmp : rTrees[y].resIdx){
rTrees[y].upd(0, 0, m-1, tmp, -1);
cTrees[tmp].upd(0, 0, n-1, y, -1);
//cerr << y << ' ' << tmp << '\n';
a[y][tmp] --;
}
}
if(c == 'E'){
rTrees[y].resIdx.clear();
rTrees[y].glR = r;
rTrees[y].getL(0, 0, m-1, h);
for(auto tmp : rTrees[y].resIdx){
rTrees[y].upd(0, 0, m-1, tmp, -1);
cTrees[tmp].upd(0, 0, n-1, y, -1);
//cerr << y << ' ' << tmp << '\n';
a[y][tmp] --;}
}
//}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
//cerr << a[i][j] << ' ';
}
//cerr << '\n';
}
cout << getMax();
}
/*4 8 2 6 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
N 2 2
W 2 2
W 2 3
E 2 1
S 4 1
S 7 1*/
Compilation message
ufo.cpp: In function 'int main()':
ufo.cpp:174:8: warning: unused variable 'tmp' [-Wunused-variable]
174 | int tmp;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
125 ms |
203884 KB |
Output is correct |
| 2 |
Correct |
127 ms |
204012 KB |
Output is correct |
| 3 |
Correct |
131 ms |
204140 KB |
Output is correct |
| 4 |
Correct |
150 ms |
204908 KB |
Output is correct |
| 5 |
Correct |
293 ms |
209516 KB |
Output is correct |
| 6 |
Correct |
451 ms |
247788 KB |
Output is correct |
| 7 |
Runtime error |
280 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
241 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
264 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
243 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
238 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
249 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
240 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
241 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
259 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
238 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
280 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
239 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
238 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
171 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
