| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338259 |
2020-12-22T20:12:40 Z |
Tosic |
UFO (IZhO14_ufo) |
C++14 |
|
249 ms |
262148 KB |
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int n, m, r, k, p;
vector<vector<int> > a, c;
vector<int> rv;
struct segtree
{
vector<int> tree;
vector<int> resIdx;
vector<int> a;
int n, glR;
segtree(){
n=0;
glR = 0;
}
void init(int sz, vector<int> tmp){
n = sz;
tree.resize(2*n+10, 0);
a = tmp;
init(0, 0, n-1);
}
void kidsO(int idx){
if(idx*2+2 >= tree.size()){
return;
}
tree[idx] = max(tree[idx*2+1], tree[idx*2+2]);
}
void init(int idx, int l, int r){
if(l == r){
tree[idx] = a[l];
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));
}
};
vector<segtree> rTrees, cTrees;
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, 0);
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cin >> a[i][j];
}
rTrees.push_back(segtree());
rTrees[i].init(m, a[i]);
}
for(int i = 0; i < m; ++i){
for(int j = 0;j<n; ++ j){
rv[j] = a[j][i];
}
cTrees.push_back(segtree());
cTrees[i].init(n, rv);
}
for(int i = 0; i < k; ++i){
char c;
int h, y;
cin >> c >> y >> h;
y--;
//for(int j = 0; j < r; ++j){
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]--;
}
cTrees[y].resIdx.clear();
}
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]--;
}
cTrees[y].resIdx.clear();
}
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] --;
}
rTrees[y].resIdx.clear();
}
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] --;}
rTrees[y].resIdx.clear();
}
//}
}
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 member function 'void segtree::kidsO(int)':
ufo.cpp:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | if(idx*2+2 >= tree.size()){
| ~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
27 ms |
1260 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
3 ms |
1516 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
11 ms |
8940 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
249 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
217 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
120 ms |
41876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
214 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
209 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
212 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
166 ms |
81516 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
224 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
218 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
209 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
193 ms |
81520 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
195 ms |
93796 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
214 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
239 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
