| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 40632 |
2018-02-06T01:28:38 Z |
faustaadp |
UFO (IZhO14_ufo) |
C++11 |
|
1994 ms |
102448 KB |
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int n,m,r,k,p,i,j,ta,tb,hv,L,R,C,hs;
char ct;
vector<vector<int> > a,str,stc,pr;
pair<int,int> hz;
void ini()
{
for(i=0;i<=n;i++)
{
vector<int> vt;
for(j=0;j<=m;j++)
vt.pb(0);
a.pb(vt);
}
for(i=0;i<=n;i++)
{
vector<int> vt;
for(j=0;j<=m;j++)
vt.pb(0);
pr.pb(vt);
}
for(i=0;i<=n;i++)
{
vector<int> vt;
for(j=0;j<=4*m;j++)
vt.pb(0);
stc.pb(vt);
}
for(i=0;i<=m;i++)
{
vector<int> vt;
for(j=0;j<=4*n;j++)
vt.pb(0);
str.pb(vt);
}
}
void upr(int aa,int bb,int cc,int dd,int ee,int ff)
{
if(aa==bb)
str[ff][ee]=dd;
else
{
int ce=(aa+bb)/2;
if(cc<=ce)
upr(aa,ce,cc,dd,ee*2,ff);
else
upr(ce+1,bb,cc,dd,ee*2+1,ff);
str[ff][ee]=max(str[ff][ee*2],str[ff][ee*2+1]);
}
}
void upc(int aa,int bb,int cc,int dd,int ee,int ff)
{
if(aa==bb)
stc[ff][ee]=dd;
else
{
int ce=(aa+bb)/2;
if(cc<=ce)
upc(aa,ce,cc,dd,ee*2,ff);
else
upc(ce+1,bb,cc,dd,ee*2+1,ff);
stc[ff][ee]=max(stc[ff][ee*2],stc[ff][ee*2+1]);
}
}
pair<int,int> nilN(int aa,int bb,int ee,int ff)
{
if(aa==bb)
return mp(aa,str[ff][ee]-1);
int ce=(aa+bb)/2;
if(str[ff][ee*2]>=tb)
return nilN(aa,ce,ee*2,ff);
else
return nilN(ce+1,bb,ee*2+1,ff);
}
pair<int,int> nilS(int aa,int bb,int ee,int ff)
{
if(aa==bb)
return mp(aa,str[ff][ee]-1);
int ce=(aa+bb)/2;
if(str[ff][ee*2+1]>=tb)
return nilS(ce+1,bb,ee*2+1,ff);
else
return nilS(aa,ce,ee*2,ff);
}
pair<int,int> nilW(int aa,int bb,int ee,int ff)
{
if(aa==bb)
return mp(aa,stc[ff][ee]-1);
int ce=(aa+bb)/2;
if(stc[ff][ee*2]>=tb)
return nilW(aa,ce,ee*2,ff);
else
return nilW(ce+1,bb,ee*2+1,ff);
}
pair<int,int> nilE(int aa,int bb,int ee,int ff)
{
if(aa==bb)
return mp(aa,stc[ff][ee]-1);
int ce=(aa+bb)/2;
if(stc[ff][ee*2+1]>=tb)
return nilE(ce+1,bb,ee*2+1,ff);
else
return nilE(aa,ce,ee*2,ff);
}
int nil(int aa,int bb,int cc,int ee,int ff)
{
if(aa==bb)
return stc[ff][ee];
else
{
int ce=(aa+bb)/2;
if(cc<=ce)
return nil(aa,ce,cc,ee*2,ff);
else
return nil(ce+1,bb,cc,ee*2+1,ff);
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>r>>k>>p;
ini();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>ta;
upr(1,n,i,ta,1,j);
upc(1,m,j,ta,1,i);
}
while(k--)
{
cin>>ct>>ta>>tb;
vector<pair<int,int> > v;
if(ct=='N')
{
for(i=1;i<=r;i++)
{
if(str[ta][1]<tb)
break;
hz=nilN(1,n,1,ta);
upr(1,n,hz.fi,-10e8,1,ta);
v.pb(hz);
}
for(i=0;i<v.size();i++)
{
upr(1,n,v[i].fi,v[i].se,1,ta);
upc(1,m,ta,v[i].se,1,v[i].fi);
}
}
else
if(ct=='S')
{
for(i=1;i<=r;i++)
{
if(str[ta][1]<tb)
break;
hz=nilS(1,n,1,ta);
upr(1,n,hz.fi,-10e8,1,ta);
v.pb(hz);
}
for(i=0;i<v.size();i++)
{
upr(1,n,v[i].fi,v[i].se,1,ta);
upc(1,m,ta,v[i].se,1,v[i].fi);
}
}
else
if(ct=='W')
{
for(i=1;i<=r;i++)
{
if(stc[ta][1]<tb)
break;
hz=nilW(1,m,1,ta);
upc(1,m,hz.fi,-10e8,1,ta);
v.pb(hz);
}
for(i=0;i<v.size();i++)
{
upr(1,n,ta,v[i].se,1,v[i].fi);
upc(1,m,v[i].fi,v[i].se,1,ta);
}
}
else
{
for(i=1;i<=r;i++)
{
if(stc[ta][1]<tb)
break;
hz=nilE(1,m,1,ta);
upc(1,m,hz.fi,-10e8,1,ta);
v.pb(hz);
}
for(i=0;i<v.size();i++)
{
upr(1,n,ta,v[i].se,1,v[i].fi);
upc(1,m,v[i].fi,v[i].se,1,ta);
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
a[i][j]=nil(1,m,j,1,i);
pr[i][j]=pr[i][j-1]+pr[i-1][j]-pr[i-1][j-1]+a[i][j];
// cout<<a[i][j]<<" ";
}
// cout<<"\n";
}
for(i=1;i+p-1<=n;i++)
for(j=1;j+p-1<=m;j++)
hs=max(hs,pr[i+p-1][j+p-1]-pr[i-1][j+p-1]-pr[i+p-1][j-1]+pr[i-1][j-1]);
cout<<hs<<"\n";
}
Compilation message
ufo.cpp: In function 'int main()':
ufo.cpp:150:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v.size();i++)
^
ufo.cpp:167:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v.size();i++)
^
ufo.cpp:184:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v.size();i++)
^
ufo.cpp:200:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v.size();i++)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
352 KB |
Output is correct |
| 3 |
Correct |
3 ms |
552 KB |
Output is correct |
| 4 |
Correct |
30 ms |
824 KB |
Output is correct |
| 5 |
Correct |
159 ms |
2868 KB |
Output is correct |
| 6 |
Correct |
368 ms |
19772 KB |
Output is correct |
| 7 |
Correct |
570 ms |
46016 KB |
Output is correct |
| 8 |
Correct |
501 ms |
46016 KB |
Output is correct |
| 9 |
Correct |
959 ms |
46016 KB |
Output is correct |
| 10 |
Correct |
1233 ms |
46016 KB |
Output is correct |
| 11 |
Correct |
905 ms |
46016 KB |
Output is correct |
| 12 |
Correct |
1251 ms |
46016 KB |
Output is correct |
| 13 |
Correct |
1401 ms |
56696 KB |
Output is correct |
| 14 |
Correct |
1093 ms |
56696 KB |
Output is correct |
| 15 |
Correct |
1228 ms |
56696 KB |
Output is correct |
| 16 |
Correct |
505 ms |
56696 KB |
Output is correct |
| 17 |
Correct |
1769 ms |
56696 KB |
Output is correct |
| 18 |
Correct |
450 ms |
56696 KB |
Output is correct |
| 19 |
Correct |
752 ms |
56696 KB |
Output is correct |
| 20 |
Correct |
1994 ms |
102448 KB |
Output is correct |
