| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338298 |
2020-12-22T21:32:57 Z |
Tosic |
UFO (IZhO14_ufo) |
C++14 |
|
1461 ms |
212380 KB |
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int n, m, r, k, p;
vector<vector<int> > a, rv;
vector<vector<long long> > c;
//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;
init1(0, 0, n-1);
}
void kidsO(int idx){
tree[idx] = max(tree[idx*2+1], tree[idx*2+2]);
}
void init1(int idx, int l, int r){
if(idx >= tree.size()){
return;
}
if(l == r){
if(isC){
tree[idx] = a[l][rowCol];
//cerr << tree[idx] << '\n';
} else {
tree[idx] = a[rowCol][l];
}
return;
}
int mid = (l+r)/2;
init1(idx*2+1, l ,mid);
init1(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;
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;
long long tmpS(int x, int y){
if(x < 0 or y < 0){
return 0;
}
return c[x][y];
}
long long 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];
}
}
long long 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<long long>(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, i, 0);
}
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, i, 1);
rv[i].clear();
}
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::init1(int, int, int)':
ufo.cpp:31:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::getF(int, int, int, int)':
ufo.cpp:49:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::getL(int, int, int, int)':
ufo.cpp:72:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
ufo.cpp:95:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'int segtree::query(int, int, int, int, int)':
ufo.cpp:113:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if(idx >= 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 |
Correct |
2 ms |
492 KB |
Output is correct |
| 4 |
Correct |
21 ms |
1004 KB |
Output is correct |
| 5 |
Correct |
127 ms |
4324 KB |
Output is correct |
| 6 |
Correct |
221 ms |
25580 KB |
Output is correct |
| 7 |
Correct |
290 ms |
65656 KB |
Output is correct |
| 8 |
Correct |
218 ms |
65984 KB |
Output is correct |
| 9 |
Correct |
535 ms |
59244 KB |
Output is correct |
| 10 |
Correct |
705 ms |
65876 KB |
Output is correct |
| 11 |
Correct |
465 ms |
67028 KB |
Output is correct |
| 12 |
Correct |
708 ms |
65832 KB |
Output is correct |
| 13 |
Correct |
862 ms |
70836 KB |
Output is correct |
| 14 |
Correct |
728 ms |
67156 KB |
Output is correct |
| 15 |
Correct |
961 ms |
66496 KB |
Output is correct |
| 16 |
Correct |
245 ms |
68772 KB |
Output is correct |
| 17 |
Correct |
1293 ms |
72008 KB |
Output is correct |
| 18 |
Correct |
235 ms |
66936 KB |
Output is correct |
| 19 |
Correct |
393 ms |
81436 KB |
Output is correct |
| 20 |
Correct |
1461 ms |
212380 KB |
Output is correct |
