| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338288 |
2020-12-22T20:50:49 Z |
Tosic |
UFO (IZhO14_ufo) |
C++14 |
|
1492 ms |
205208 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;
vector<int> *a;
int n, glR;
segtree(){
}
void init(int sz, vector<int>& tmp){
n = sz;
tree.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]);
}
void init(int idx, int l, int r){
if(idx >= tree.size()){
return;
}
if(l == r){
tree[idx] = a->at(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){
a->at(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(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:28:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::getF(int, int, int, int)':
ufo.cpp:41:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::getL(int, int, int, int)':
ufo.cpp:64:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
ufo.cpp:87:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | if(idx >= tree.size()){
| ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'int segtree::query(int, int, int, int, int)':
ufo.cpp:106:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | 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 |
18 ms |
876 KB |
Output is correct |
| 5 |
Correct |
114 ms |
4064 KB |
Output is correct |
| 6 |
Correct |
213 ms |
22380 KB |
Output is correct |
| 7 |
Correct |
289 ms |
60236 KB |
Output is correct |
| 8 |
Correct |
212 ms |
59724 KB |
Output is correct |
| 9 |
Correct |
508 ms |
53140 KB |
Output is correct |
| 10 |
Correct |
676 ms |
60108 KB |
Output is correct |
| 11 |
Correct |
453 ms |
61948 KB |
Output is correct |
| 12 |
Correct |
695 ms |
60236 KB |
Output is correct |
| 13 |
Correct |
853 ms |
63076 KB |
Output is correct |
| 14 |
Correct |
712 ms |
61820 KB |
Output is correct |
| 15 |
Correct |
850 ms |
59724 KB |
Output is correct |
| 16 |
Correct |
236 ms |
61436 KB |
Output is correct |
| 17 |
Correct |
1325 ms |
63308 KB |
Output is correct |
| 18 |
Correct |
227 ms |
61304 KB |
Output is correct |
| 19 |
Correct |
400 ms |
74544 KB |
Output is correct |
| 20 |
Correct |
1492 ms |
205208 KB |
Output is correct |
