| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338286 |
2020-12-22T20:48:18 Z |
Tosic |
UFO (IZhO14_ufo) |
C++14 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int n, m, r, k, p;
vector<vector<int> > a, c, rv;
//vector<int> rv;
struct segtree
{
vector<int> tree;
vector<int> resIdx;
bool isC;
int rowCol;
int n, glR;
segtree(){
}
void init(int sz, int rowCol, bool isC){
n = sz;
tree.resize(4*n+10, 0);
this->isC = isC;
this->rowCol = rowCol;
init(0, 0, n-1);
}
void kidsO(int idx){
tree[idx] = max(tree[idx*2+1], tree[idx*2+2]);
}
void init(int idx, int l, int r){
if(idx >= tree.size()){
return;
}
if(l == r){
if(isC){
tree[idx] = a[l][rowCol];
} else {
tree[idx] = a[rowCol][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){
if(idx >= tree.size()){
return;
}
// 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){
if(idx >= tree.size()){
return;
}
// 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(idx >= tree.size()){
return;
}
if(l == r){
tree[idx] += newV;
if(isC){
a[l][rowCol] += newV;
} else {
a[rowCol][l] += 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(idx >= tree.size()){
return 0;
}
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, vector<int>(n));
//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[i][j] = a[j][i];
}
cTrees.push_back(segtree());
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){
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::init(int, int, int)':
ufo.cpp:30:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::getF(int, int, int, int)':
ufo.cpp:47:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::getL(int, int, int, int)':
ufo.cpp:70:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
ufo.cpp:93:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'int segtree::query(int, int, int, int, int)':
ufo.cpp:116:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In function 'int main()':
ufo.cpp:181:25: error: no matching function for call to 'segtree::init(int&, __gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type&)'
181 | rTrees[i].init(m, a[i]);
| ^
ufo.cpp:19:7: note: candidate: 'void segtree::init(int, int, bool)'
19 | void init(int sz, int rowCol, bool isC){
| ^~~~
ufo.cpp:19:7: note: candidate expects 3 arguments, 2 provided
ufo.cpp:29:7: note: candidate: 'void segtree::init(int, int, int)'
29 | void init(int idx, int l, int r){
| ^~~~
ufo.cpp:29:7: note: candidate expects 3 arguments, 2 provided
ufo.cpp:188:26: error: no matching function for call to 'segtree::init(int&, __gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type&)'
188 | cTrees[i].init(n, rv[i]);
| ^
ufo.cpp:19:7: note: candidate: 'void segtree::init(int, int, bool)'
19 | void init(int sz, int rowCol, bool isC){
| ^~~~
ufo.cpp:19:7: note: candidate expects 3 arguments, 2 provided
ufo.cpp:29:7: note: candidate: 'void segtree::init(int, int, int)'
29 | void init(int idx, int l, int r){
| ^~~~
ufo.cpp:29:7: note: candidate expects 3 arguments, 2 provided
