| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581209 |
2022-06-22T11:35:17 Z |
FatihSolak |
UFO (IZhO14_ufo) |
C++17 |
|
1129 ms |
106568 KB |
#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct SegTree{
vector<int> t;
int n;
SegTree(int size){
n = size;
t.assign(4*n,0);
}
void upd(int v,int tl,int tr,int pos,int val){
if(tl == tr){
t[v] = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm)
upd(v*2,tl,tm,pos,val);
else upd(v*2+1,tm+1,tr,pos,val);
t[v] = max(t[v*2],t[v*2+1]);
}
int get1(int v,int tl,int tr,int l,int r,int val){
if(tr < l || r < tl)
return -1;
if(t[v] < val)
return -1;
if(tl == tr)
return tl;
int tm = (tl + tr)/2;
int tmp = get1(v*2,tl,tm,l,r,val);
if(tmp == -1)
return get1(v*2+1,tm+1,tr,l,r,val);
return tmp;
}
int get2(int v,int tl,int tr,int l,int r,int val){
if(tr < l || r < tl)
return -1;
if(t[v] < val)
return -1;
if(tl == tr)
return tl;
int tm = (tl + tr)/2;
int tmp = get2(v*2+1,tm+1,tr,l,r,val);
if(tmp == -1)
return get2(v*2,tl,tm,l,r,val);
return tmp;
}
void upd(int pos,int val){
upd(1,1,n,pos,val);
}
int get1(int l,int r,int val){
return get1(1,1,n,l,r,val);
}
int get2(int l,int r,int val){
return get2(1,1,n,l,r,val);
}
};
vector<vector<int>> v;
vector<SegTree> row,col;
void upd(int i,int j){
row[i].upd(j,v[i][j]);
col[j].upd(i,v[i][j]);
}
void solve(){
int n,m,r,k,p;
cin >> n >> m >> r >> k >> p;
v = vector<vector<int>>(n+1,vector<int>(m+1,0));
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin >> v[i][j];
}
}
for(int i = 0;i<=n;i++){
row.push_back(SegTree(m));
}
for(int i = 0;i<=m;i++){
col.push_back(SegTree(n));
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
upd(i,j);
}
}
for(int i = 1;i<=k;i++){
char type;
int x,h;
cin >> type >> x >> h;
if(type == 'W'){
vector<int> pts;
int last = 0;
while(row[x].get1(last+1,m,h) != -1 && pts.size() != r){
pts.push_back(row[x].get1(last+1,m,h));
last = pts.back();
}
for(auto u:pts){
v[x][u]--;
upd(x,u);
}
}
if(type == 'E'){
vector<int> pts;
int last = m+1;
while(row[x].get2(1,last-1,h) != -1 && pts.size() != r){
pts.push_back(row[x].get2(1,last-1,h));
last = pts.back();
}
for(auto u:pts){
v[x][u]--;
upd(x,u);
}
}
if(type == 'N'){
vector<int> pts;
int last = 0;
while(col[x].get1(last+1,n,h) != -1 && pts.size() != r){
pts.push_back(col[x].get1(last+1,n,h));
last = pts.back();
}
for(auto u:pts){
v[u][x]--;
upd(u,x);
}
}
if(type == 'S'){
vector<int> pts;
int last = n+1;
while(col[x].get2(1,last-1,h) != -1 && pts.size() != r){
pts.push_back(col[x].get2(1,last-1,h));
last = pts.back();
}
for(auto u:pts){
v[u][x]--;
upd(u,x);
}
}
}
// for(int i = 1;i<=n;i++){
// for(int j = 1;j<=m;j++){
// cout << v[i][j] << " ";
// }
// cout << "\n";
// }
int ans = 0;
for(int i = 1;i+p-1<=n;i++){
for(int j = 1;j+p-1<=m;j++){
int sum = 0;
for(int c = i;c<=i+p-1;c++){
for(int d = j;d<=j+p-1;d++){
sum += v[c][d];
}
}
ans = max(ans,sum);
}
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while(t--){
solve();
}
#ifdef Local
cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
#endif
}
Compilation message
ufo.cpp: In function 'void solve()':
ufo.cpp:91:63: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
91 | while(row[x].get1(last+1,m,h) != -1 && pts.size() != r){
| ~~~~~~~~~~~^~~~
ufo.cpp:103:63: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | while(row[x].get2(1,last-1,h) != -1 && pts.size() != r){
| ~~~~~~~~~~~^~~~
ufo.cpp:115:63: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
115 | while(col[x].get1(last+1,n,h) != -1 && pts.size() != r){
| ~~~~~~~~~~~^~~~
ufo.cpp:127:63: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
127 | while(col[x].get2(1,last-1,h) != -1 && pts.size() != r){
| ~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
220 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
20 ms |
724 KB |
Output is correct |
| 5 |
Correct |
106 ms |
3036 KB |
Output is correct |
| 6 |
Correct |
220 ms |
20948 KB |
Output is correct |
| 7 |
Correct |
291 ms |
50176 KB |
Output is correct |
| 8 |
Correct |
226 ms |
46580 KB |
Output is correct |
| 9 |
Correct |
531 ms |
42432 KB |
Output is correct |
| 10 |
Correct |
646 ms |
45680 KB |
Output is correct |
| 11 |
Correct |
449 ms |
45228 KB |
Output is correct |
| 12 |
Correct |
663 ms |
45688 KB |
Output is correct |
| 13 |
Correct |
771 ms |
50880 KB |
Output is correct |
| 14 |
Correct |
555 ms |
45480 KB |
Output is correct |
| 15 |
Correct |
707 ms |
47224 KB |
Output is correct |
| 16 |
Correct |
247 ms |
47528 KB |
Output is correct |
| 17 |
Correct |
1109 ms |
55344 KB |
Output is correct |
| 18 |
Correct |
231 ms |
48032 KB |
Output is correct |
| 19 |
Correct |
410 ms |
53872 KB |
Output is correct |
| 20 |
Correct |
1129 ms |
106568 KB |
Output is correct |
