| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 341147 |
2020-12-29T04:08:04 Z |
juggernaut |
UFO (IZhO14_ufo) |
C++14 |
|
1561 ms |
133484 KB |
#include<bits/stdc++.h>
using namespace std;
int remain;
vector<int>vec;
struct data{
vector<int>t;
void reset(int n){t.resize(n<<2);}
void update(int v,int tl,int tr,int pos, int val){
if(tl==tr){
t[v]=val;
return;
}
int mid=(tl+tr)>>1;
if(pos<=mid)update(v<<1,tl,mid,pos,val);
else update(v<<1|1,mid+1,tr,pos,val);
t[v]=max(t[v<<1],t[v<<1|1]);
}
void findfirst(int v,int tl,int tr,int x){
if(remain==0||t[v]<x)return;
if(tl==tr){
remain--;
vec.push_back(tl);
return;
}
int mid=(tl+tr)>>1;
findfirst(v<<1,tl,mid,x);
findfirst(v<<1|1,mid+1,tr,x);
}
void findlast(int v,int tl,int tr,int x){
if(remain==0||t[v]<x)return;
if(tl==tr){
remain--;
vec.push_back(tl);
return;
}
int mid=(tl+tr)>>1;
findlast(v<<1|1,mid+1,tr,x);
findlast(v<<1,tl,mid,x);
}
};
data row[1000005],col[1000005];
int main(){
int n,m,r,k,p;
scanf("%d%d%d%d%d",&n,&m,&r,&k,&p);
int a[n+5][m+5];
memset(a,0,sizeof(a));
for(int i=1;i<=m;i++)col[i].reset(n+1);
for(int i=1;i<=n;i++){
row[i].reset(m+1);
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
row[i].update(1,1,m,j,a[i][j]);
col[j].update(1,1,n,i,a[i][j]);
}
}
char ch;
int id,h;
while(k--){
vec.clear();
remain=r;
cin>>ch;
scanf("%d%d", &id, &h);
if(ch=='W'){
row[id].findfirst(1,1,m,h);
for(auto to:vec){
a[id][to]--;
row[id].update(1,1,m,to,a[id][to]);
col[to].update(1,1,n,id,a[id][to]);
}
}
if(ch=='N'){
col[id].findfirst(1,1,n,h);
for(auto to:vec){
a[to][id]--;
row[to].update(1,1,m,id,a[to][id]);
col[id].update(1,1,n,to,a[to][id]);
}
}
if(ch=='E'){
row[id].findlast(1,1,m,h);
for(auto to:vec){
a[id][to]--;
row[id].update(1,1,m,to,a[id][to]);
col[to].update(1,1,n,id,a[id][to]);
}
}
if(ch=='S'){
col[id].findlast(1,1,n,h);
for(auto to:vec){
a[to][id]--;
row[to].update(1,1,m,id,a[to][id]);
col[id].update(1,1,n,to,a[to][id]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x=0,y=0;
if(j>=2)y=a[i][j-1];
if(i>=2)x=a[i-1][j];
a[i][j]=a[i][j]+x+y-a[i-1][j-1];
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(i>=p&&j>=p)
ans=max(ans,a[i][j]-a[i][j-p]-a[i-p][j]+a[i-p][j-p]);
cout<<ans;
}
Compilation message
ufo.cpp: In function 'int main()':
ufo.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
44 | scanf("%d%d%d%d%d",&n,&m,&r,&k,&p);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
51 | scanf("%d",&a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~
ufo.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
62 | scanf("%d%d", &id, &h);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
47340 KB |
Output is correct |
| 2 |
Correct |
30 ms |
47340 KB |
Output is correct |
| 3 |
Correct |
32 ms |
47340 KB |
Output is correct |
| 4 |
Correct |
47 ms |
47596 KB |
Output is correct |
| 5 |
Correct |
135 ms |
49260 KB |
Output is correct |
| 6 |
Correct |
307 ms |
64588 KB |
Output is correct |
| 7 |
Correct |
445 ms |
87660 KB |
Output is correct |
| 8 |
Correct |
407 ms |
87660 KB |
Output is correct |
| 9 |
Correct |
664 ms |
85228 KB |
Output is correct |
| 10 |
Correct |
779 ms |
87660 KB |
Output is correct |
| 11 |
Correct |
573 ms |
87148 KB |
Output is correct |
| 12 |
Correct |
804 ms |
87780 KB |
Output is correct |
| 13 |
Correct |
977 ms |
87660 KB |
Output is correct |
| 14 |
Correct |
827 ms |
87276 KB |
Output is correct |
| 15 |
Correct |
969 ms |
87660 KB |
Output is correct |
| 16 |
Correct |
410 ms |
87148 KB |
Output is correct |
| 17 |
Correct |
1392 ms |
87532 KB |
Output is correct |
| 18 |
Correct |
388 ms |
83180 KB |
Output is correct |
| 19 |
Correct |
540 ms |
92652 KB |
Output is correct |
| 20 |
Correct |
1561 ms |
133484 KB |
Output is correct |
