| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171972 |
2019-12-30T17:39:30 Z |
Swan |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
149084 KB |
#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
//#define int long long
using namespace std;
const int maxn = 100004;
int n,m,r,k,p;
bool f;
/*WE-0 NS-1*/
vector<vector<int> > tree[4];
vector<vector<int> > pref;
void increment(int dir,int num,int v,int l,int r,int need,int val){
if(l == r){
tree[dir][num][v]+=val;
return;
}
int m = (l+r)/2;
if(need<=m)increment(dir,num,v*2,l,m,need,val);
else increment(dir,num,v*2+1,m+1,r,need,val);
tree[dir][num][v] = max(tree[dir][num][v*2],tree[dir][num][v*2+1]);
}
int find_on_segm_l(int dir,int num,int v,int l,int r,int need){
if(l == r){
f = 1;
return l;
}
int m = (l+r)/2;
if(tree[dir][num][v*2]>=need)return find_on_segm_l(dir,num,v*2,l,m,need);
else if(tree[dir][num][v*2+1]>=need)return find_on_segm_l(dir,num,v*2+1,m+1,r,need);
else return -1;
}
int find_on_segm_r(int dir,int num,int v,int l,int r,int need){
if(l == r){
f = 1;
return l;
}
int m = (l+r)/2;
if(tree[dir][num][v*2+1]>=need)return find_on_segm_r(dir,num,v*2+1,m+1,r,need);
else if(tree[dir][num][v*2]>=need)return find_on_segm_r(dir,num,v*2,l,m,need);
else return -1;
}
int get_max_l(int dir,int num,int v,int l,int r,int le,int re,int need){
if(l >= le && r <= re ){
if(tree[dir][num][v]>=need && !f)return find_on_segm_l(dir,num,v,l,r,need);
else return -1;
}
if(l > re || r < le)return -1;
int m = (l+r)/2;
int a,b;
a = get_max_l(dir,num,v*2,l,m,le,re,need);
b = get_max_l(dir,num,v*2+1,m+1,r,le,re,need);
if(a!= -1)return a;
else return b;
}
int get_max_r(int dir,int num,int v,int l,int r,int le,int re,int need){
if(l >= le && r <= re){
if(tree[dir][num][v]>=need && !f)return find_on_segm_r(dir,num,v,l,r,need);
else return -1;
}
if(l > re || r < le)return -1;
int m = (l+r)/2;
int a,b;
b = get_max_r(dir,num,v*2+1,m+1,r,le,re,need);
a = get_max_r(dir,num,v*2,l,m,le,re,need);
if(b!= -1)return b;
else return a;
}
int get_cell(int v,int l,int r,int x,int y){
if(l == r)return tree[0][x][v];
int m = (l+r)/2;
if(y<=m)return get_cell(v*2,l,m,x,y);
else return get_cell(v*2+1,m+1,r,x,y);
}
void update_cell(int x,int y,int val){
increment(0,x,1,0,m-1,y,val);
increment(1,y,1,0,n-1,x,val);
}
void solve_w(int x,int need){
int cnt = r;
int l,r;l = 0;r = m-1;
while(cnt && (l!=m)){
f = 0;
int w = get_max_l(0,x,1,0,m-1,l,r,need);
if(w == -1)break;
cnt--;
l = w;
update_cell(x,l,-1);
l++;
}
}
void solve_e(int x,int need){
int cnt = r;
int l,r;l = 0;r = m-1;
while(cnt && (r>=0)){
f = 0;
int w = get_max_r(0,x,1,0,m-1,l,r,need);
if(w == -1)break;
cnt--;
r = w;
update_cell(x,r,-1);
r--;
}
}
void solve_n(int x,int need){
int cnt = r;
int l,r;l = 0;r = n-1;
while(cnt && (l!=n)){
f = 0;
int w = get_max_l(1,x,1,0,n-1,l,r,need);
if(w == -1)break;
cnt--;
l = w;
update_cell(l,x,-1);
l++;
}
}
void solve_s(int x,int need){
int cnt = r;
int l,r;l = 0;r = n-1;
while(cnt && (r>=0)){
f = 0;
int w = get_max_r(1,x,1,0,n-1,l,r,need);
if(w == -1)break;
cnt--;
r = w;
update_cell(r,x,-1);
r--;
}
}
void print(){
for(int i(0); i < n;i++){
for(int j(0); j < m;j++){
int now = get_cell(1,0,m-1,i,j);
int tox = i+1;int toy = j+1;
pref[tox][toy] = now;
pref[tox][toy]+=pref[tox-1][toy];
pref[tox][toy]+=pref[tox][toy-1];
pref[tox][toy]-=pref[tox-1][toy-1];
}
}
}
int get_sum(int x1,int y1,int x2,int y2){
int res = 0;
res+=pref[x2][y2];
res-=pref[x2][y1-1];
res-=pref[x1-1][y2];
res+=pref[x1-1][y1-1];
return res;
}
main(){
ios_base::sync_with_stdio(0);
cin >> n >> m >> r >> k >> p;
pref.resize(n+2);
for(int i(0); i <= n;i++)pref[i].resize(m+2);
tree[0].resize(n);
tree[1].resize(m);
tree[2].resize(n);
tree[3].resize(m);
for(int i(0); i < n;i++){
tree[0][i].resize(4*m);
tree[2][i].resize(4*m);
}
for(int i(0); i < m;i++){
tree[1][i].resize(4*n);
tree[3][i].resize(4*n);
}
for(int i(0); i < n;i++){
for(int j(0); j < m;j++){
int val; cin >> val;
update_cell(i,j,val);
}
}
for(int i(0); i < k;i++){
char c; cin >> c;
int x,need; cin >> x >> need;
x--;
if(c == 'W')solve_w(x,need);
if(c == 'E')solve_e(x,need);
if(c == 'N')solve_n(x,need);
if(c == 'S')solve_s(x,need);
}
print();
int ans = 0;
for(int i(1);i<=n;i++){
for(int j(1);j<=m;j++){
int x1 = i;
int y1 = j;
int x2 = i+p-1;
int y2 = j+p-1;
if(x2 <= n && y2<=m)ans = max(ans,get_sum(x1,y1,x2,y2));
}
}
cout << ans;
return 0;
}
/*
*/
Compilation message
ufo.cpp:171:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
632 KB |
Output is correct |
| 4 |
Correct |
55 ms |
1016 KB |
Output is correct |
| 5 |
Correct |
192 ms |
4088 KB |
Output is correct |
| 6 |
Correct |
452 ms |
33144 KB |
Output is correct |
| 7 |
Correct |
752 ms |
75200 KB |
Output is correct |
| 8 |
Correct |
672 ms |
75188 KB |
Output is correct |
| 9 |
Correct |
1208 ms |
71160 KB |
Output is correct |
| 10 |
Correct |
1640 ms |
75128 KB |
Output is correct |
| 11 |
Correct |
1113 ms |
74180 KB |
Output is correct |
| 12 |
Correct |
1657 ms |
75316 KB |
Output is correct |
| 13 |
Correct |
1779 ms |
79608 KB |
Output is correct |
| 14 |
Correct |
1459 ms |
74180 KB |
Output is correct |
| 15 |
Correct |
1576 ms |
75196 KB |
Output is correct |
| 16 |
Correct |
664 ms |
74180 KB |
Output is correct |
| 17 |
Execution timed out |
2033 ms |
79352 KB |
Time limit exceeded |
| 18 |
Correct |
521 ms |
70776 KB |
Output is correct |
| 19 |
Correct |
996 ms |
83408 KB |
Output is correct |
| 20 |
Execution timed out |
2070 ms |
149084 KB |
Time limit exceeded |
