| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 83492 |
2018-11-08T10:39:18 Z |
ToadDaveski |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
263168 KB |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
map <ll,map <ll,ll> > h,v,a,ans,dp;
void build(ll x,ll l,ll r,ll type,ll i)
{
if (l==r)
{
//cout<<"| ";
if (type==1){
h[i][x]=a[i][l];
//cout<<h[i][x]<<" h "<<i<<" "<<l;
}
else {
v[i][x]=a[l][i];
//cout<<v[i][x]<<" v "<<l<<" "<<i;
}
//cout<<endl;
}
else
{
ll bm=(l+r)/2;
build(x*2,l,bm,type,i);
build(x*2+1,bm+1,r,type,i);
if (type==1)
h[i][x]=max(h[i][x*2],h[i][x*2+1]);
else v[i][x]=max(v[i][x*2],v[i][x*2+1]);
}
}
ll findans(ll x,ll l,ll r,ll tl, ll tr,ll i,ll height,ll type)
{
//cout<<x<<" "<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<i<<" "<<type<<" ";
//if (type<=2) cout<<h[i][x]<<endl;
//else cout<<v[i][x]<<endl;
if (type<=2 && h[i][x]<height)
if (type==1) return 1e12;
else return -1;
if (type>=3 && v[i][x]<height)
if (type==3) return 1e12;
else return -1;
if (l==r)
{
if (type<=2){
if (h[i][x]>=height)
{
// cout<<"nashelnahui "<<l<<endl;
if (tl==l) return l;
if (type==1) return 1e9;
else return -1;
}
}
else{
if (v[i][x]>=height)
{
// cout<<"nashelnahui "<<l<<endl;
if (tl==l) return l;
if (type==3) return 1e9;
else return -1;
}
}
return -1;
}
ll bm=(l+r)/2;
//cout<<"zaebalblyat";
if (type==1 || type==3)
return min(findans(x*2,l,bm,tl,min(bm,tr),i,height,type),findans(x*2+1,bm+1,r,max(tl,bm+1),tr,i,height,type));
if (type==2 || type==4)
return max(findans(x*2,l,bm,tl,min(bm,tr),i,height,type),findans(x*2+1,bm+1,r,max(tl,bm+1),tr,i,height,type));
}
void update(ll x,ll l,ll r,ll i,ll poz,ll type)
{
//cout<<l<<" update "<<r<<" "<<poz<<endl;
if (l==r)
{
if (type==1)
h[i][x]--;
else v[i][x]--;
//cout<<"#"<<l<<" update "<<h[i][x]<<" "<<v[i][x]<<endl;
}
else
{
ll bm=(l+r)/2;
if (l<=poz && poz<=bm)
update(x*2,l,bm,i,poz,type);
else update(x*2+1,bm+1,r,i,poz,type);
if (type==1)
h[i][x]=max(h[i][x*2],h[i][x*2+1]);
else v[i][x]=max(v[i][x*2],v[i][x*2+1]);
}
}
void makeup(ll x,ll l,ll r,ll i)
{
if (l==r)
{
ans[l][i]=v[i][x];
// cout<<v[i][x]<<"#"<<endl;
}
else
{
ll bm=(l+r)/2;
makeup(x*2,l,bm,i);
makeup(x*2+1,bm+1,r,i);
}
}
int main()
{
ll n,m,R,k,P,i,j;
cin>>n>>m>>R>>k>>P;
//k--;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
ll x;
cin>>x;
a[i][j]=x;
}
for(i=1;i<=n;i++)
build(1,1,m,1,i);
for(i=1;i<=m;i++)
build(1,1,n,2,i);
//cout<<3<<endl;
while(k--)
{
char c;
ll type;
cin>>c;
if (c=='W') type=1;
if (c=='E') type=2;
if (c=='N') type=3;
if (c=='S') type=4;
ll x,y;
cin>>x>>y;
if (type==1 || type==2)
{
ll tl=1,tr=m;
for(j=1;j<=R;j++)
{
ll f=findans(1,1,m,tl,tr,x,y,type);
// cout<<f<<endl;
if (f==-1 || f==1e12) continue;
update(1,1,m,x,f,1);
update(1,1,n,f,x,2);
if (type==1) tl=f+1;
else tr=f-1;
}
}
if (type==3 || type==4)
{
ll tl=1,tr=n;
for(j=1;j<=R;j++)
{
// cout<<3<<endl;
ll f=findans(1,1,n,tl,tr,x,y,type);
if (f==-1 || f==1e12) continue;
update(1,1,n,x,f,2);
update(1,1,m,f,x,1);
if (type==3) tl=f+1;
else tr=f-1;
}
}
}
for(i=1;i<=m;i++)
makeup(1,1,n,i);
for(i=1;i<=n;i++)
{
ll sum=0;
for(j=1;j<=m;j++)
{
sum+=ans[i][j];
dp[i][j]=dp[i-1][j]+sum;
}
}
//cout<<endl;
/*for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<ans[i][j]<<" ";
cout<<endl;
}*/
ll answer=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
{
// cout<<dp[i][j]<<" ";
if (i<P || j<P)
continue;
answer=max(answer,dp[i][j]-(dp[i][j-P]+dp[i-P][j]-dp[i-P][j-P]));
}
//cout<<endl;
}
cout<<answer;
return 0;
}
Compilation message
ufo.cpp: In function 'long long int findans(long long int, long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
ufo.cpp:35:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if (type<=2 && h[i][x]<height)
^
ufo.cpp:38:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if (type>=3 && v[i][x]<height)
^
ufo.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
ufo.cpp: In function 'int main()':
ufo.cpp:126:12: warning: 'type' may be used uninitialized in this function [-Wmaybe-uninitialized]
ll type;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
644 KB |
Output isn't correct |
| 3 |
Incorrect |
30 ms |
1908 KB |
Output isn't correct |
| 4 |
Incorrect |
1227 ms |
5340 KB |
Output isn't correct |
| 5 |
Execution timed out |
2071 ms |
17300 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2060 ms |
157868 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2081 ms |
263168 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2020 ms |
263168 KB |
Time limit exceeded |
| 9 |
Runtime error |
1855 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
1926 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
1910 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
1966 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Execution timed out |
2083 ms |
263168 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2069 ms |
263168 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2045 ms |
263168 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2052 ms |
263168 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2088 ms |
263168 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2075 ms |
263168 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2025 ms |
263168 KB |
Time limit exceeded |
| 20 |
Runtime error |
1957 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
