| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171949 |
2019-12-30T16:46:16 Z |
Swan |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
78584 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;
/*WE-0 NS-1*/
vector<vector<int> > tree[2];
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){
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){
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)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)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;
a = get_max_r(dir,num,v*2,l,m,le,re,need);
b = get_max_r(dir,num,v*2+1,m+1,r,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)){
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)){
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)){
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)){
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(){
scanf("%d%d%d%d%d",&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);
for(int i(0); i < n;i++){
tree[0][i].resize(4*m);
}
for(int i(0); i < m;i++){
tree[1][i].resize(4*n);
}
for(int i(0); i < n;i++){
for(int j(0); j < m;j++){
int val; scanf("%d",&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));
}
}
printf("%d",ans);
return 0;
}
/*
*/
Compilation message
ufo.cpp:164:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
ufo.cpp: In function 'int main()':
ufo.cpp:165:10: 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:178:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int val; scanf("%d",&val);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
504 KB |
Output is correct |
| 4 |
Correct |
45 ms |
760 KB |
Output is correct |
| 5 |
Correct |
260 ms |
2992 KB |
Output is correct |
| 6 |
Correct |
552 ms |
18680 KB |
Output is correct |
| 7 |
Correct |
929 ms |
41572 KB |
Output is correct |
| 8 |
Correct |
774 ms |
40916 KB |
Output is correct |
| 9 |
Correct |
1324 ms |
38692 KB |
Output is correct |
| 10 |
Correct |
1827 ms |
40852 KB |
Output is correct |
| 11 |
Correct |
1268 ms |
40312 KB |
Output is correct |
| 12 |
Correct |
1881 ms |
40828 KB |
Output is correct |
| 13 |
Execution timed out |
2053 ms |
45176 KB |
Time limit exceeded |
| 14 |
Correct |
1718 ms |
40300 KB |
Output is correct |
| 15 |
Correct |
1875 ms |
40564 KB |
Output is correct |
| 16 |
Correct |
874 ms |
40056 KB |
Output is correct |
| 17 |
Execution timed out |
2060 ms |
45800 KB |
Time limit exceeded |
| 18 |
Correct |
754 ms |
40464 KB |
Output is correct |
| 19 |
Correct |
1243 ms |
44920 KB |
Output is correct |
| 20 |
Execution timed out |
2061 ms |
78584 KB |
Time limit exceeded |
