| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 103265 |
2019-03-29T11:52:56 Z |
brcode |
UFO (IZhO14_ufo) |
C++14 |
|
1670 ms |
188680 KB |
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e6 + 5;
int n,m,r,k,p;
vector<vector<int>> a;
vector<int> temp;
int remain;
struct segtree{
vector<int> v1;
int n;
void reset(int n) {
this -> n = n;
v1.resize((n * 6) + 10);
}
void update(int curr,int l,int r,int u,int val){
// cout<<l<<" "<<r<<endl;
if(l == r){
v1[curr] = val;
return;
}
int mid = (l+r)/2;
if(u<=mid){
update(2*curr,l,mid,u,val);
}else{
update(2*curr+1,mid+1,r,u,val);
}
v1[curr] = max(v1[2*curr],v1[2*curr+1]);
}
void findfirst(int curr,int l,int r,int x){
if(remain == 0||v1[curr]<x){
//cout<<l<<" "<<r<<" "<<v1[curr]<<endl;
return;
}
if(l == r){
remain--;
temp.push_back(l);
}else{
int mid = (l+r)/2;
findfirst(2*curr,l,mid,x);
findfirst(2*curr+1,mid+1,r,x);
}
}
void findlast(int curr,int l,int r,int x){
if(remain == 0||v1[curr]<x){
return;
}
if(l == r){
remain--;
temp.push_back(l);
}else{
int mid = (l+r)/2;
findlast(2*curr+1,mid+1,r,x);
findlast(2*curr,l,mid,x);
}
}
};
segtree row[MAXN],col[MAXN];
int main(){
cin>>m>>n>>r>>k>>p;
a.resize(m+1);
for(int i=1;i<=n;i++){
col[i].reset(m+1);
}
a[0].resize(n+1);
for(int i=1;i<=m;i++){
row[i].reset(n+1);
a[i].resize(n+1);
for(int j=1;j<=n;j++){
cin>>a[i][j];
row[i].update(1,1,n,j,a[i][j]);
col[j].update(1,1,m,i,a[i][j]);
}
}
for(int i=0;i<k;i++){
temp.clear();
remain = r;
char z;
cin>>z;
int id,h;
cin>>id>>h;
if(z == 'W'){
row[id].findfirst(1,1,n,h);
for(int x:temp){
//cout<<x<<endl;1,
a[id][x]--;
row[id].update(1,1,n,x,a[id][x]);
col[x].update(1,1,m,id,a[id][x]);
}
}else if(z == 'E'){
row[id].findlast(1,1,n,h);
for(int x:temp){
a[id][x]--;
row[id].update(1,1,n,x,a[id][x]);
col[x].update(1,1,m,id,a[id][x]);
}
}else if(z == 'N'){
col[id].findfirst(1,1,m,h);
for(int x:temp){
a[x][id]--;
row[x].update(1,1,n,id,a[x][id]);
col[id].update(1,1,m,x,a[x][id]);
}
}else{
col[id].findlast(1,1,m,h);
for(int x:temp){
a[x][id]--;
//cout<<x<<endl;
row[x].update(1,1,n,id,a[x][id]);
col[id].update(1,1,m,x,a[x][id]);
}
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
int ans = 0;
for(int i=1;i<=m-p+1;i++){
for(int j=1;j<=n-p+1;j++){
if(i+p-1>m||j+p-1>n){
continue;
}
int temp = a[i+p-1][j+p-1] - a[i+p-1][j-1] - a[i-1][j+p-1] + a[i-1][j-1];
ans = max(ans,temp);
}
}
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
62968 KB |
Output is correct |
| 2 |
Correct |
92 ms |
62968 KB |
Output is correct |
| 3 |
Correct |
57 ms |
63096 KB |
Output is correct |
| 4 |
Correct |
76 ms |
63608 KB |
Output is correct |
| 5 |
Correct |
180 ms |
66296 KB |
Output is correct |
| 6 |
Correct |
459 ms |
88440 KB |
Output is correct |
| 7 |
Correct |
776 ms |
122836 KB |
Output is correct |
| 8 |
Correct |
660 ms |
122828 KB |
Output is correct |
| 9 |
Correct |
868 ms |
118648 KB |
Output is correct |
| 10 |
Correct |
1029 ms |
122872 KB |
Output is correct |
| 11 |
Correct |
810 ms |
122488 KB |
Output is correct |
| 12 |
Correct |
1002 ms |
122648 KB |
Output is correct |
| 13 |
Correct |
952 ms |
126984 KB |
Output is correct |
| 14 |
Correct |
951 ms |
122360 KB |
Output is correct |
| 15 |
Correct |
1014 ms |
122748 KB |
Output is correct |
| 16 |
Correct |
786 ms |
122340 KB |
Output is correct |
| 17 |
Correct |
1670 ms |
127060 KB |
Output is correct |
| 18 |
Correct |
779 ms |
119788 KB |
Output is correct |
| 19 |
Correct |
935 ms |
129636 KB |
Output is correct |
| 20 |
Correct |
1564 ms |
188680 KB |
Output is correct |
