| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 5691 |
2014-05-13T07:11:08 Z |
cki86201 |
UFO (IZhO14_ufo) |
C++ |
|
1719 ms |
76260 KB |
#include<stdio.h>
#include<vector>
using namespace std;
vector<vector <int> > inp;
int N, M, R, K, P;
struct node{
node(){v=x=0,link[0]=link[1]=0;}
int v, x;
node *link[2];
inline void pushup(){
x = max(v, max(link[0] ? link[0]->x : 0, link[1] ? link[1]->x : 0));
}
void build(int xy,int cl,int s,int d){
int m = (s+d) >> 1;
v = (xy ? inp[m][cl] : inp[cl][m]);
if(s<m){
link[0] = new node();
link[0]->build(xy, cl, s, m-1);
}
if(m<d){
link[1] = new node();
link[1]->build(xy, cl, m+1, d);
}
pushup();
}
void update(int w,int s,int d){
int m = (s+d)>>1;
if(w == m)--v;
else if(w<m)link[0]->update(w, s, m-1);
else link[1]->update(w, m+1, d);
pushup();
}
int get_min(int h,int s,int d,int L){
if(x < h)return -1;
int m = (s+d)>>1;
if(link[0] && L < m-1){
int t = link[0]->get_min(h, s, m-1, L);
if(t != -1)return t;
}
if(L < m && v >= h)return m;
if(link[1]){
int t = link[1]->get_min(h, m+1, d, L);
if(t != -1)return t;
}
return -1;
}
int get_max(int h,int s,int d,int L){
if(x < h)return -1;
int m = (s+d)>>1;
if(link[1] && L > m+1){
int t = link[1]->get_max(h, m+1, d, L);
if(t != -1)return t;
}
if(L > m && v >= h)return m;
if(link[0]){
int t = link[0]->get_max(h, s, m-1, L);
if(t != -1)return t;
}
return -1;
}
};
vector <node*> xr, yr;
void update(int x,int y)
{
inp[x][y]--;
xr[x]->update(y, 0, M-1);
yr[y]->update(x, 0, N-1);
}
int main()
{
scanf("%d%d%d%d%d",&N,&M,&R,&K,&P);
int i, j;
inp.resize(N);
for(i=0;i<N;i++){
inp[i].resize(M);
for(j=0;j<M;j++)scanf("%d",&inp[i][j]);
}
xr.resize(N), yr.resize(M);
for(i=0;i<N;i++)xr[i] = new node(), xr[i]->build(0, i, 0, M-1);
for(i=0;i<M;i++)yr[i] = new node(), yr[i]->build(1, i, 0, N-1);
for(int tt=0;tt<K;tt++){
char c[2];
int w, h;
scanf("%s%d%d",c,&w,&h);
--w;
if(c[0] == 'N'){
int t = -1;
for(i=0;i<R;i++){
t = yr[w]->get_min(h, 0, N-1, t);
if(t == -1)break;
update(t, w);
}
}
else if(c[0] == 'S'){
int t = N;
for(i=0;i<R;i++){
t = yr[w]->get_max(h, 0, N-1, t);
if(t == -1)break;
update(t, w);
}
}
else if(c[0] == 'W'){
int t = -1;
for(i=0;i<R;i++){
t = xr[w]->get_min(h, 0, M-1, t);
if(t == -1)break;
update(w, t);
}
}
else{
int t = M;
for(i=0;i<R;i++){
t = xr[w]->get_max(h, 0, M-1, t);
if(t == -1)break;
update(w, t);
}
}
}
for(i=0;i<N;i++){
int sum = 0;
for(j=0;j<P;j++)sum += inp[i][j];
int save = inp[i][0];
inp[i][0] = sum;
for(j=0;j<M-P;j++){
sum += inp[i][j+P] - save;
save = inp[i][j+1];
inp[i][j+1] = sum;
}
}
for(j=0;j<M-P+1;j++){
int sum = 0;
for(i=0;i<P;i++)sum += inp[i][j];
int save = inp[0][j];
inp[0][j] = sum;
for(i=0;i<N-P;i++){
sum += inp[i+P][j] - save;
save = inp[i+1][j];
inp[i+1][j] = sum;
}
}
int ans = 0;
for(i=0;i<N-P+1;i++)for(j=0;j<M-P+1;j++)ans = max(ans, inp[i][j]);
printf("%d",ans);
return 0;
}
Compilation message
ufo.cpp: In function 'int main()':
ufo.cpp:76:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d",&N,&M,&R,&K,&P);
^
ufo.cpp:81:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(j=0;j<M;j++)scanf("%d",&inp[i][j]);
^
ufo.cpp:89:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%d%d",c,&w,&h);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1968 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1968 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2232 KB |
Output is correct |
| 4 |
Correct |
16 ms |
2628 KB |
Output is correct |
| 5 |
Correct |
113 ms |
5408 KB |
Output is correct |
| 6 |
Correct |
376 ms |
34572 KB |
Output is correct |
| 7 |
Correct |
376 ms |
69240 KB |
Output is correct |
| 8 |
Correct |
259 ms |
69240 KB |
Output is correct |
| 9 |
Correct |
696 ms |
68848 KB |
Output is correct |
| 10 |
Correct |
726 ms |
69240 KB |
Output is correct |
| 11 |
Correct |
556 ms |
66744 KB |
Output is correct |
| 12 |
Correct |
789 ms |
69240 KB |
Output is correct |
| 13 |
Correct |
899 ms |
72284 KB |
Output is correct |
| 14 |
Correct |
679 ms |
66744 KB |
Output is correct |
| 15 |
Correct |
979 ms |
69240 KB |
Output is correct |
| 16 |
Correct |
329 ms |
66744 KB |
Output is correct |
| 17 |
Correct |
1719 ms |
72284 KB |
Output is correct |
| 18 |
Correct |
329 ms |
63804 KB |
Output is correct |
| 19 |
Correct |
403 ms |
70020 KB |
Output is correct |
| 20 |
Correct |
1036 ms |
76260 KB |
Output is correct |
